LeetCode 4. 寻找两个有序数组的中位数

发表于 | 更新于 | 分类于

题意

给出两个有序数组，在时间复杂度$O(log(m + n))$内求出这两个数组的中位数。

思路

  • 这个题目印象深刻，我在王道数据结构上做过，感觉是比每章给出的思维拓展题都要好的一道题目。与那道题不同的是，这道题两组数据给出的元素个数是可以不一样的。
  • 根据数组有序 + 对复杂度的要求，很明显是要通过二分查找来实现。具体操作如下：
    • 为了方便讨论，我们记num1数组为A，num2数组为B，并假设A.size() $\leq $ B.size()。
    • 假设通过划分使得A分为了leftA和rightA，B分为了leftB和rightB，则满足题意的情况就是len(leftA) + len(leftB) == len(rightA) + len(rightB) && max(leftA) $\leq$ min(rightB) && max(leftB) $\leq$ min(rightA)。
    • 我们通过对A数组二分查找来划分数组，并不断判断条件是否满足。记i为当前访问的A的位置，j为当前访问的B的位置，则由上述关系可知，$j = \frac{m+n+1}{2} - i$。
    • 最后处理一下边界情况 & n + m的奇偶情况。前者是通过设置最大值最小值来完成的，后者是特殊判断了一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2, nums1);
        int m = nums1.size();
        int n = nums2.size();
        int low = 0, high = m;
        while(low <= high)
        {
            int i = low + high >> 1;
            int j = (m + n + 1) / 2 - i;

            int maxleftA = i == 0 ? INT_MIN : nums1[i - 1];
            int minrightA = i == m ? INT_MAX : nums1[i];

            int maxleftB = j == 0 ? INT_MIN : nums2[j - 1];
            int minrightB = j == n ? INT_MAX : nums2[j];

            if(maxleftA <= minrightB && maxleftB <= minrightA)
            {
                if((m + n) & 1)
                    return 1.0 * max(maxleftA, maxleftB);
                else
                    return (max(maxleftA, maxleftB) + min(minrightA, minrightB)) / 2.0;
            }
            else if(maxleftA > minrightB)
                high = i - 1;
            else
                low = i + 1;
        }
        return 0.0;
    }
};

总结

一直觉得有好多细节要考虑，于是迟迟没动键盘(难道这就是你咕了一年的原因？)。

Donate comment here
0%