知识点

递归 分治

思路

两个有序数组，一个长度为n，一个长度为m，找到两个数组归并后的中位数。

根据中位数的定义，假如m+n是奇数，那么需要找到第(n+m)/2+1小的数作为答案；假如是偶数，那么需要找到第(n + m) /2 小的数和(n+m)/2+1小的数的平均数作为中位数。

因此我们需要实现一个函数find可以在log时间内找到两个有序数组的第k小的数。

对于找两个有序数组的第k小数的函数 find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)：

其中i是第一个数组第一个可以选的位置, j是第二个数组第一个可以选的位置

首先，假如两个有序数组中的剩余未选的元素个数均大于等于k/2，那么我们先在两个数组的剩余元素中先各选k/2个

  • 如果在nums1数组中本次选出的k/2个元素的最大元素大于nums2数组本次选出的k/2个元素的最大元素，这说明nums2应该再多选点，nums1应该少选点，进一步我们知道nums2这k/2个元素是一定要选出的，那么下一次只需要在剩余的元素中选出

k - k/2个元素，问题规模变成了原问题的一半

  • 假如不满足上面这一条，那么nums1的这k/2个元素是一定要选出的，那么下一次只需要在剩余的元素中选出k - k/2个元素，问题规模变成了原问题的一半

考虑边界情况，假如有一个数组不足够取k/2个元素了，那么把剩余的元素全取；当k=1时选取两个数组中可以选择的最小元素即可

实现上始终让nums1作为备选元素少的一个数组用来简化计算。

时间复杂度

由于用分治思想，每次可以解决原问题的一半，时间复杂度为O(log(n+m))

AC code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型vector 
     * @param weightsB int整型vector 
     * @return double浮点型
     */
    double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        int tot = weightsA.size() + weightsB.size();
        if (!(tot & 1)) {
            int left = find(weightsA, 0, weightsB, 0, tot / 2);
            int right = find(weightsB, 0, weightsA, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        }
        return find(weightsA, 0, weightsB, 0, tot / 2 + 1);
    }
    double find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min(i + k / 2, (int)nums1.size()), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1]) return find(nums1, i, nums2, sj, k - (sj - j));
        else return find(nums1, si, nums2, j, k - (si - i));
    }
};