【LeetCode-4】寻找两个正序数组的中位数

问题

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

示例

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2

解答

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        int left = (len + 1) / 2, right = (len + 2) / 2; // len为奇数时，left == right
        return (findKth(nums1, nums2, 0, 0, left) + findKth(nums1, nums2, 0, 0, right)) / 2;
    }
private:
    double findKth(vector<int>& nums1, vector<int>& nums2,  int l1, int l2, int k) { // 求两个数组合并后的第k小
        if (l1 >= nums1.size()) return nums2[l2 + k - 1];
        if (l2 >= nums2.size()) return nums1[l1 + k - 1];
        if (k == 1) return min(nums1[l1], nums2[l2]);
        int half = k / 2;
        int mid1 = (l1 + half - 1 < nums1.size()) ? nums1[l1 + half - 1] : INT_MAX;
        int mid2 = (l2 + half - 1 < nums2.size()) ? nums2[l2 + half - 1] : INT_MAX;
        if (mid1 < mid2) return findKth(nums1, nums2, l1 + half, l2, k - half);
        else return findKth(nums1, nums2, l1, l2 + half, k - half);
    }
};

重点思路

我们要求两个数组合并后的第k小，可以使用二分的方法，逐步删除不满足要求的子数组。方法为：比较两个数组的第k / 2项，根据其关系选择删除的部分。

• 当此时nums1和nums2的长度都大于k / 2时：

  • 如果nums1[k / 2 - 1] > nums2[k / 2 - 1]，则删除nums2的前k / 2项。证明： 我们用反证法，如果第k小的数在nums2的前k / 2项中，那么我们要求的数必定是nums2[k / 2 - 1]，这就要求nums1[k / 2 - 1] <= nums2[k / 2 - 1]且nums1和nums2的长度都大于k / 2，第一个要求与前提矛盾，所以必定不在nums2的前k / 2项中；
  • 反之删除nums1的前k / 2项。

• 当此时nums1和nums2的长度存在小于k / 2时（设nums1.size() < k / 2）：

  • 直接删除nums2的前k / 2项。证明： 我们用反证法，如果第k小的数在nums2的前k / 2项中，那么我们要求的数必定是nums2[k / 2 - 1]，这就要求nums1[k / 2 - 1] <= nums2[k / 2 - 1]且nums1和nums2的长度都大于k / 2，第二个要求与前提矛盾，所以必定不在nums2的前k / 2项中；

本题有两个终止条件：

• k == 1时，输出此时的min(nums1[0], nums2[0])；
• 一个数组被删光了，那只需要返回另一个数组的第k个。

【LeetCode-4】寻找两个正序数组的中位数

原文：https://www.cnblogs.com/tmpUser/p/14633206.html