[LC]4.寻找两个正序数组的中位数

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

分析

暴力解

直接归并两个有序数组，然后求中位数即可

时间复杂度 ：$O(m+n)$

二分查找

先考虑更一般的问题，找第$k$小的数。

为了找到第$k$小的数，先考虑$A[k/2 - 1]$和$B[k/2 - 1]$，这分为三种情况：

1. $A[k/2 - 1] < B[k/2 - 1]$ :

   $命题:A[0,1,…,k/2-1]中的数不会是第k小的数$

   $证明:A[k/2 - 1]是A[0,1,…,k/2-1]中最大的数，$

   $而A[k/2-1]之前最多有k/2-1+k/2-1 = k-2个元素,$

   $因此A[k/2-1]至多是第k-1小的元素.$

   因此，对于此种情况，我们丢弃$A[0,1,…,k/2-1]$中的元素，并相应的更新$k$，求解一个规模更小的子问题.

2. $A[k/2 - 1] > B[k / 2 -1]$

   同理，对于此种情况，我们丢弃$B[0,1,…,k/2-1]$中的元素，并相应的更新$k$.

3. $A[k/2-1] = B[k/2 -1]$

   该情况可以并入情况1.

需要注意的是，我们必须考虑当$k/2-1$越界的情况，此时我们取数组最后一个元素即可，更新$k$的时候要相应的修改。

当$k=1$的时候，我们只需要返回两个数组首元素中的较小者即可。

代码

class Solution {
public:
    // k 从1开始
    double findKthElement(const vector<int>& nums1, 
                          const vector<int>& nums2, 
                          size_t k)
    {
    	size_t l1 = 0, l2 = 0, m = nums1.size(), n = nums2.size();
        while (true)
        {
            if (l1 == m)
            	return nums2[l2 + k - 1];
            if (l2 == n)
                return nums1[l1 + k - 1];
            if (k == 1)
                return min(nums1[l1], nums2[l2]);
        	size_t m1 = min(l1 + k/2 - 1, m - 1);
            size_t m2 = min(l2 + k/2 - 1, n - 1);
            if (nums1[m1] <= nums2[m2])
            {
                k -= (m1 - l1 + 1);
                l1 = m1 + 1;
            }
            else
            {
                k -= (m2 - l2 + 1);
                l2 = m2 + 1;
            }
		}
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
      	size_t length = nums1.size() + nums2.size();
        if (length % 2 == 1)
            return findKthElement(nums1, nums2, length / 2 + 1);
        else
            return (findKthElement(nums1, nums2, length / 2) + 
                    findKthElement(nums1, nums2, length / 2 + 1)) / 2.0;
    }
    
};

时间复杂度：

因为每次$k$都会减少一半，所以时间复杂度为$O(logk) = O(log(m+n)).$