雅乐网

题目

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

思路

两个排序数组找中位数，如果用类似归并排序merge的方式可以找到中间的数字，时间复杂度为O(m+n)。

本题目要求时间复杂度为O(log(m+n))，只能考虑利用已排序的特点直接按下标寻值，而不是遍历。

n个数字寻找中位数需要寻找第n/2或者n/2和n/2+1两个位置的数字，关键是如何寻找两个数组的第k小元素。

先从两个数组中一共取出k个元素，第一个数组取第k1小，第二个数组取弟k2( = k – k1)小

这样就把两个数组分成了4个部分，其中A<B, C<D

如果v1 == v2，那么它的值就正好是第k小。

如果v1<v2，那么我们可以肯定第k小的元素不会在A中，类似的v1>v2时，可以排除C

这样就把问题的规模缩小了

代码

class Solution {
public:
    int findK(vector<int>::iterator nums1, int len1, vector<int>::iterator nums2, int len2, int k)
	{
        // 我们只需要考虑nums1长度比nums2小的情况
        if (len1 > len2)
            return findK(nums2, len2, nums1, len1, k);
        
        // 递归基
        // 其中一个数组为空时 直接返回
        // k==1时直接比较返回
        if (len1 == 0)
            return nums2[k-1];
        if (len2 == 0)
            return nums1[k-1];
        if (k == 1)
            return min(nums1[0], nums2[0]);
        
        // 考虑k/2大于数组长度的情况
        int k1 = k/2 > len1 ? len1 : k/2;
        int k2 = k - k1;
        
        int v1 = nums1[k1-1];
        int v2 = nums2[k2-1];
        
        if (v1 < v2)
            return findK(nums1 + k1, len1 - k1, nums2, len2, k - k1);
        else if (v1 > v2)
            return findK(nums1, len1, nums2 + k2, len2 - k2, k-k2);
        else
            return v1;
    }
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int l1 = nums1.size();
		int l2 = nums2.size();
		int n = l1 + l2;
		if (n % 2 == 0)
		{
			int f1 = findK(nums1.begin(), l1, nums2.begin(), l2, n / 2);
			int f2 = findK(nums1.begin(), l1, nums2.begin(), l2, n / 2 + 1);
			return (f1 +f2) / 2.0;
		}
		else
			return findK(nums1.begin(), l1, nums2.begin(), l2, n / 2 + 1);
	}
};