Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

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)).

Thoughts

https://www.youtube.com/watch?v=KB9IcSCDQ9k

让nums1为长度更短的数组, 它们俩长度分别为n1和n2. 找整个排好序的中位数即整个排好序的第k = (n1 + n2 + 1) / 2个. k个中有nums1中的m1个(index到m1 - 1)和num2中的m2 = k - m1个(index到m2 - 1). 为了找出m1和m2是多少, 不难想到可以用两个指针分别指向num1和num2的0位置, 当nums1[m1]小时m1++, 否则m2++. 这么做的时间复杂度是O((n1 + n2) / 2). 我们可以对此过程继续优化.

m1表示把nums1和nums2合并排序后从头到median中nums1的个数, m2 = k - m1 为nums2元素的个数. 对于一共m1 + m2 = k个，如果m1取少了，m2取多了，把在num2中比整个中位数还大的也放进去了，此时一定满足nums1[m1] < nums[m2]。因此利用二分法, 当nums[m1] < nums[m2]时, 如果再往左移动则前k个会把比nums[m2]更大的加进去，所以m1只能继续往右边移动。反之同理。 m1和m2一直代表个数, 二分结束时m1和m2分别指向候选中位元素的下一个。 当k为奇数时, 需要从m1左和m2左中挑一个返回, 由于它们都在k里, 最后一个一定是它们中较大的那个。当k为偶数时, 还要把m1和m2中多选一个然后和k - 1中最大的相加 / 2。

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const auto N1 = nums1.size(), N2 = nums2.size();
        // 长的作nums2, 因为后面找nums2中元素时要-1，会出现负数。
        if (N1 > N2) return findMedianSortedArrays(nums2, nums1); 
        int k = (N1 + N2 + 1) / 2, start = 0, end = N1;
        // m1和m2是个数。
        while (start < end) {
            int m1 = start + (end - start) / 2, m2 = k - m1;
            if (nums1[m1] < nums2[m2 - 1]) {
                start = m1 + 1;  
            } else {
                end = m1;
            }
        }
        // 因为是个数，现在指向的都是候选者下一位
        int m1 = start;
        int m2 = k - m1;
        const double c1 = max(m1 == 0 ? INT_MIN : nums1[m1 - 1], m2 == 0 ? INT_MIN : nums2[m2 - 1]);
        if ((N1 + N2) % 2 == 1) return c1; // 此时中位数是k - 1 = m1 + m2 - 1的位置
        const double c2 = min(m1 == N1 ? INT_MAX : nums1[m1], m2 == N2 ? INT_MAX : nums2[m2]);
        return (c1 + c2) / 2;
    }
};

Analysis

时间复杂度O(min(lgn1, lgn2)).