LeetCode 4. Median of Two Sorted Arrays

问题链接

题目解析

给定两个有序的数组，找到两个数组的中位数。

解题思路

虽然两个数组都是有序的，要找到其中位数确实有点麻烦，因为两个数组不能简简单单合并起来。

采用最暴力的方法，开一个新向量，把两个数组都放进去，重新排序，然后取其中位数。然而这种方法的时间复杂度是 (n+m)log(n+m) ，不符合题目要求。虽然可以AC，但时间确实久了些，只能打败10%的人，只能说LeetCode的时间判断有毒，参考代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<long long> V;
        V.clear();
        if(nums1.size() == 0 && nums2.size() == 0) return 0.0;
        else
        {
            for (int i = 0; i < nums1.size(); ++i) V.push_back(nums1[i]);
            for (int i = 0; i < nums2.size(); ++i) V.push_back(nums2[i]);
            sort(V.begin(), V.end());

            double ans = 0.0;
            int len = V.size();
            if (len % 2 == 0)
                ans = ((double)V[len / 2] + V[len / 2 - 1]) / 2;
            else
                ans = (double)V[len / 2];

            return ans;
        }
    }
};

二分解法（一）

所以，题目要求的 log(n+m) 算法到底是什么呢？大概可以猜出需要使用二分法，在两个数组里使用二分法，这就是这道题的Hard点了。官方题解：median-of-two-sorted-arrays/solution/，其中讲的比较清楚，有图有说明，注意最后的JAVA代码有点小bug，评论中也有说明。

巧妙地运用中位数的性质，将所有数分成相等的两份，两个指针i、j之间关系确定，通过二分找到合适的 i ，再考虑奇偶问题。不过说实话对于二分我一直有一种害怕，总是不能明白循环终止时具体什么情况。

JAVA参考代码，已修改小bug：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) { // to ensure m<=n
            int[] temp = nums1; nums1 = nums2; nums2 = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && nums2[j-1] > nums1[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && nums1[i-1] > nums2[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = nums2[j-1]; }
                else if (j == 0) { maxLeft = nums1[i-1]; }
                else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = nums2[j]; }
                else if (j == n) { minRight = nums1[i]; }
                else { minRight = Math.min(nums2[j], nums1[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

二分解法（二）

本题还有另一种巧妙解法，参考：巧妙解法(https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation)。分析下来，其实是解法一中的改进版本，思路是一样的。

同样是二分，其实道理和上面一样，用两个指针（mid1和mid2）分别切割两个数组，不过这里换了一种解释方法，假设数组两边有一个极小值和极大值，避免了边界问题。同时转化了中位数的概念，利用分割左值L和右值R，使得奇数和偶数可以不加区分。

时间复杂度：$O(log(min(m,n)))，又快有准。参考代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m < n) return findMedianSortedArrays(nums2, nums1);
        if (n == 0) return ((double)nums1[(m - 1) / 2] + (double)nums1[m / 2]) / 2.0;
        int left = 0, right = n * 2;
        while (left <= right) {
            int mid2 = (left + right) / 2;
            int mid1 = m + n - mid2;
            double L1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2];
            double L2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2];
            double R1 = mid1 == m * 2 ? INT_MAX : nums1[mid1 / 2];
            double R2 = mid2 == n * 2 ? INT_MAX : nums2[mid2 / 2];
            if (L1 > R2) left = mid2 + 1;
            else if (L2 > R1) right = mid2 - 1;
            else return (max(L1, L2) + min(R1, R2)) / 2;
        }
        return -1;
    }
};

巧妙解法

参考链接：寻找第k小，[LeetCode] Median of Two Sorted Arrays中解法一类似。将问题转化成寻找第K小的数。

时间复杂度：O(log(m+n))。参考代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        } else {
            return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2;
        }
    }
    double findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return findKth(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int pa = min(i + k / 2, int(nums1.size())), pb = j + k - pa + i;
        if (nums1[pa - 1] < nums2[pb - 1]) 
            return findKth(nums1, pa, nums2, j, k - pa + i);
        else if (nums1[pa - 1] > nums2[pb - 1]) 
            return findKth(nums1, i, nums2, pb, k - pb + j);
        else 
            return nums1[pa - 1];
    }
};

我细致想了想，后面所讲的三种方法其实核心思想相同，具体实现有所不同，不知道大家理解了没有？个人认为第二个代码最好理解，你觉得呢？

LeetCode All in One题解汇总（持续更新中...）

本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

秒客网