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

题目

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

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

分析

暴力解

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

时间复杂度 ：$$

二分查找

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

为了找到第$$小的数，先考虑$$和$$，这分为三种情况：

1. $$ :

   $$

   $$

   $$

   $$

   因此，对于此种情况，我们丢弃$$中的元素，并相应的更新$$，求解一个规模更小的子问题.

2. $$

   同理，对于此种情况，我们丢弃$$中的元素，并相应的更新$$.

3. $$

   该情况可以并入情况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;
    }
    
};
C++

时间复杂度：

因为每次$$都会减少一半，所以时间复杂度为$$