Median of Two Sorted Arrays两数相加寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

---

输入：

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

输出：

2.0

---

输入：

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

输出：

2.5

---

分析
限制条件：时间复杂度O(log(m+n))。很明显，只有用到二分的方法才能达到这个时间复杂度。我们不妨用另一种思路，题目是求中位数，其实就是求第 k 小数的一种特殊情况。

• 当m+n个数和为奇数时，中位数即第(m+n+1)/2个数。
• 当m+n个数和为偶数时，中位数即第(m+n)/2个数与(m+n)/2+1个数的平均值。

m, n奇偶不确定？找第(m+n+1)/2和第(m+n+2)/2个数，求均值即可。
即：求第k=(m+n+1)/2小的数，和求第k’=(m+n+2)/2小的数

由于数列是有序的，其实我们完全可以对k二分。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。
如果

nums1=[1,3,5,7]
nums2=[1,2,3,4,5,6,7,8,9]

此时,k=(4+9+1)/2=7。中位数为第7小的数字。
那么，我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 3 个数字。nums1数组中的 5和nums2数组中的 3。
因为3更小，因此说明nums2数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。再将[1,3,5,7]和[4,5,6,7,8,9] 两个数组作为新的数组进行比较。k值也应该更新为k-k/2;

二分法
对谁二分？对k二分。即求数组中是否存在第k/2个数字
M,N奇偶不确定？找第(m+n+1)/2和第(m+n+2)/2个数即可。

---

class Solution {
public:
    //找第(m+n+1)/2和第(m+n+2)/2个数
    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;
    }
    
    int findKth(vector<int>& nums1, int i, 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 midVal1,midVal2;
        if (i + k / 2 - 1 < nums1.size())
            midVal1 = nums1[i + k / 2 - 1];
        else midVal1= INT_MAX;   
        if (j + k / 2 - 1 < nums2.size())
            midVal2 = nums2[j + k / 2 - 1];
        else midVal2 = INT_MAX;
        //舍去哪一半？
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
};

---

相关标签：
数组 二分查找 分治算法