[LeetCode]4. Median of Two Sorted Arrays

Problem

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0
Example 2:

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

The median is (2 + 3)/2 = 2.5

给定两个有序数组nums1和nums2, 大小分别为m和n. 查找两个数组合并后的中位数. 要求时间复杂度为O(log(m+n)).

可以假设nums1和nums2不可能同时为空.

Solution

Analysis

中位数, 如果m+n为奇数,中位数正好是中间位置的数; 如果是偶数, 那么是中间位置两个数的平均值.

有序数组 + 时间复杂度O(log(m+n)). 解法应该是二分查找法. 那么之后的关注点就是如何在两个有序数组上使用二分查找法. 如果是一个数组,肯定没有难度. 二分查找,这里查找的目标是中位数, 由于m+n奇偶性的不确定性, 这里使用一个小trick, 分别查找第(m+n+1)/2, (m+n+2)/2个数. 当m+n是奇数时, 这两个查找位置相同; 当是偶数时, 这两个查找位置相邻,正好是生成中位数的元素位置.

所以,问题变为,给定两个有序数组, 如何查找合并后的第k个数. 如果能实现这个函数接口,之后直接调用即可.

二分查找, 有序数组: 两个有序数组, 查找目标: 第k个数. 我们先考虑corner cases. 具体来说,

nums1和nums2可能有个数组为空: 此时,直接在非空数组中返回第k个数;
如果k==1, 那么直接返回nums1[i]和nums2[j]的较小值即可.
一般情况, nums1和nums2都不为空,而且k!=1.这是难点, 也是主要关注的对象.

如果nums1和nums2都不为空, 我们查找nums1和nums2合并后的数组的第k个数.我们不能直接合并,因为不符合时间复杂度要求. 只能使用二分查找,对谁二分?

对k二分.分别在nums1和nums2中查找第k/2个数, 如果超过数组范围,返回一个notvalid值, 否则返回对应的值; 如果两个都是有效的, 通过mid1, mid2比较, 如果mid1 < mid2, 那么nums1的mid开始左半块都无需关注, 肯定不是查找值: 我们想象有k个坑,然后nums1的mid小于nums2的mid, 两个合并起来才是k个数, 所以nums1的mid往左都无需关注. 之后反复递归, 直到上面的两个corner cases,说明找到,返回结果.

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        
        int left = (m+n+1)/2, right = (m+n+2)/2;
        
        return (findKth(nums1,0,nums2,0, left) + findKth(nums1, 0, nums2, 0,right))/2.0;
    }
private:// i, j指定数组的起始位置, 不是一直为0.
    int findKth(const vector<int>& nums1, int i, const vector<int>& nums2, int j, int k){
        if (i >= nums1.size()) return nums2[j + k -1];
        if (j >= nums2.size()) return nums1[i + k -1];
        
        if (k == 1) return min(nums1[i], nums2[j]);
        
        int val1 = (i + k/2 -1 >= nums1.size() ? INT_MAX : nums1[i + k/2 -1]);
        int val2 = (j + k/2 -1 >= nums2.size() ? INT_MAX : nums2[j + k/2 -1]);
        
        // 查找的第k个数,变为查找k-k/2, 因为已经过滤掉了k/2个数; 同时这里必须用减法,不能使用k/2表示
        // 因为由于整数除法的取整性 1/2 = 0, 会导致使用k/2查找出错.
        if (val1 < val2)
            return findKth(nums1, i+k/2, nums2, j, k - k/2);
        else
            return findKth(nums1, i, nums2, j+k/2, k -k/2);
    }
};

References

https://www.cnblogs.com/grandyang/p/4465932.html

Problem

Solution

Analysis

Code

References

推荐文章（由hexo文章推荐插件驱动）