LeetCode 刷题之寻找两个正序数组的中位数

LeetCode 刷题之寻找两个正序数组的中位数

Chris Yue No Comment
Posts

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3) / 2 = 2.5

解题思路

这个题目就有点拗口,中位数的概念,就是一堆数里面,相对『靠近中间』的那一个(或者两个,取平均值)。其实『靠近中间』我一开始有两个解读,一个是靠近所有值的平均值,另一个是将所有数排序后,靠近中间的名次。

到底应该怎么理解,一开始我也不知道,第一次尝试就先按第二种方式来理解。使用 PHP 内置的数组函数也好处理,先 array_merge 然后 sort,最后找到排序靠中间的一个数或者两个数,运行并提交,居然就直接通过了……

当时的代码我就不发出来了,因为首先很简单没啥好发的;其次,效率和内存占用得分都不太好。我很吃惊,难道还有比用 PHP 内置函数帮忙处理还要好的方法吗?

不过通过测试也说明我一开始对中位数的理解的猜测是对的。

再重新回到题目,会发现这个题有一个特点:给定的两个数组,本身就是按顺序排好的。第一次尝试,并没有利用这个特点。另外,题目也专门提到了时间复杂度为 O(log(m+n)),即所花时间随两个数组的长度而变长,但并不是随长度等比例增加,而是 log(m+n),即消耗时间增长得比数组的长度增长还要慢一点点。

偷瞄了一下答案,再加上我自己的一些想法,思路总结如下:

两个数组去找中位数,其实就是在这两堆数里面,找到大小排名第 n 名的数(如果总个数是奇数,n 是总个数加 1 的一半;否则,n 是两个数,总数的一半,和总数的一半加 1)。

而要找到排第 n 名的数,就要先找到排 n – 1 名的数,并把它从两个数组中去掉,再从剩下的数中找出排第一的数,就是 n。

说道这,套娃的感觉是不是出来了?说道套娃,递归的感觉是不是出来了。

不过开始写代码前,我们再来想另外一个问题,我们是否真的需要一步步排除 n – 1 名的数?我觉得这是理解这道题,或者说二分法的一个很重要的点

我们先想简单的例子,在 3 个数里面排除一个数:

A, B
C

我们先对比两个数组中的第一个数。考虑到两个数组本身也排过序,不难想到,如果 A 和 C 中有一个数比较小,那么它一定是所有数最小的那个,它应当被排除。实际上,还有一种特殊情况需要考虑进去,假如 A 和 C 相等,则随便排除一个。

但如果我们把数字个数稍微增加多一点,比如:

A, B, C, D
E, F, G

总共 7 个数字,必须排除 3 个。我们是不是可以直接通过两个数组第二个数字来判断?如果我们比较了 B 和 F,发现 B 比 F 小,我们最多可以排除几个数?答案是可以一下排除两个数:我们假设 B 不可排除,则 B 至少得排第四,此时只有可能 A、E、F 或者 G 比 B 小,但已经发现 F 比 B 大,G 就更不可能比 B 小,所以 B 不可能最少排第四,是可以被排除的,此时 A 毫无疑问,也应当被排除。

当我们做了很多这样的试验之后,可以发现,当必须排除的数字为 n 个时,我们可以直接用 n / 2 这个位置的数做对比,并且可以直接排除掉比较小那个数,及它之前的所有数。

第二天编辑:这道题我后来又做了一些优化:

  1. PHP array_poparray_shift 效率要高一点点,如果在两种方法都可以解决问题的前提下,为了效率可以尽量选择第一个函数,修改之后,的确高分出现的机率要稍微高那么一点点,最好情况甚至出现过 99.7% + 100% 的情况
  2. 回到上面我们说的二分法。如果遇到二分之后,某个数组的总数都不到二分要求的个数时,其实更好的做法是将不够对比的数从另外一个数组里补,这样效率会更高一些。举一最简例, 1 和 2,3,4,5 这两组数,第一次对比的时候,本来应该是从这两组里一共选 3 个出来对比,但因为第一组只有一个数,所以第二组可以直接拿 3 出来对比,如果是 1 和 2…7 来对比,则第二组应该用 4 来对比。虽然改之后结果反而变得更不好了,但我怎么想都认为理论上这是一个有用的优化。测试的结果只是针对 LeetCode 提供的测试数据运行出来的而已,有点偏差也正常。

最终代码:

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Float
     */
    function findMedianSortedArrays($nums1, $nums2) {
        $mid = (count($nums1) + count($nums2)) / 2;

        if (is_float($mid)) {
            return self::find($nums1, $nums2, (int) ceil($mid));
        }

        return (self::find($nums1, $nums2, $mid) + self::find($nums1, $nums2, 1)) / 2;
    }

    static function find(&$nums1, &$nums2, $seq) {
        $c1 = count($nums1);
        $c2 = count($nums2);
        if ($c1 > $c2) {
            [$nums1, $nums2, $c1, $c2] = [$nums2, $nums1, $c2, $c1];
        }

        if (0 === $c1) {
            if ($seq > 1) {
                $nums2 = array_slice($nums2, 0, 1 - $seq);
            }

            return array_pop($nums2);
        }

        if (1 === $seq) {
            return end($nums1) > end($nums2) ? array_pop($nums1) : array_pop($nums2);
        }

        $offset1 = $seq / 2;
        $offset2 = (int) ceil($offset1);

        $offset1 = (int) $offset1;
        if ($offset1 > $c1) {
            $offset2 += $offset1 - $c1;
            $offset1 = $c1;
        }

        $index1 = $c1 - $offset1;
        $index2 = $c2 - $offset2;

        if ($nums1[$index1] >= $nums2[$index2]) {
            $seq -= $offset1;
            $nums1 = 0 === $index1 ? [] : array_slice($nums1, 0, $index1);
        } else {
            $seq -= $offset2;
            $nums2 = array_slice($nums2, 0, $index2);
        }

        return self::find($nums1, $nums2, $seq);
    }
}

如果有人仔细看过代码,会发现我反复 count 数组好多次,似乎可以用一个变量缓存,来提升运行效率。其实我这么做是为了让内存占用好看一点,对比使用变量保存 count 结果,这么写内存占用排名很高(能到 100%,但也会抖动比较厉害),而执行效率几乎不影响(~95%)。

LeetCode 刷题之寻找两个正序数组的中位数 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

微信赞赏码

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人

发表评论

31 − = 21