LeetCode第4题——寻找两个正序数组的中位数

题目链接

寻找两个正序数组的中位数

解法 直接排序法

对于这道题，最直接粗暴的办法是把两个数组合并起来排序，然后直接肝出新数组的中位数即答案。但是时间复杂度无法达标，为 O ( ( n + m ) l o g ( n + m ) ) O((n+m)log(n+m)) O((n+m)log(n+m)).

class Solution {
public:
    double findMedianSortedArrays(vector &nums1, vector &nums2) {
        vector ans;
        ans.resize(nums1.size() + nums2.size());
        merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), ans.begin());
        sort(ans.begin(), ans.end());
        int len = ans.size();
        if (len % 2 == 1)
            return ans[len / 2];
        else
            return (double) (ans[len / 2] + ans[len / 2 - 1]) / 2;
    }
};

递归法（ O ( l o g ( m + n ) ) O(log(m+n)) O(log(m+n))）

原问题有点难以递归，我们不妨考虑一个比较简单的问题：

在两个大小分别为n和m的有序数组中，找出总排名第k小的数.

如果这个问题可以解决，那么只要找到第 ( n + m ) / 2 (n+m)/2 (n+m)/2 大的数字即是我们所求的中位数（元素总数是奇数没问题，是偶数的话需要找到第 ( n + m ) / 2 (n+m)/2 (n+m)/2 大与第 ( n + m ) / 2 + 1 (n+m)/2+1 (n+m)/2+1 大的数字取平均，但我们现在先不用考虑这么多）。

先考虑最简单的情况，两个数组的元素数量均充足，即 n , m ≥ k / 2 n,mgeq k/2 n,m≥k/2，我们就可以先在每个数组里各取 k / 2 k/2 k/2个元素：

如果 n u m s 1 [ k / 2 − 1 ] > n u m s 2 [ k / 2 − 1 ] nums1[k/2 - 1] > nums2[k/2-1] nums1[k/2−1]>nums2[k/2−1] ，则说明在 n u m s 2 nums2 nums2 数组中，前 k / 2 k/2 k/2 个元素都小于第 k k k小的数字，可能还有“漏网之鱼”；而在 n u m s 1 nums1 nums1数组的前 k / 2 k/2 k/2 个元素中，可能有比第 k k k 小的数字大的数字被我们误取。所以我们的办法是，将 n u m s 2 nums2 nums2的前 k / 2 k/2 k/2个元素全部拿走（因为已知它们都小于第 k k k 小个数字，不是我们要找的），将问题递归成在剩下的数字中寻找第 k − [ k / 2 ] k-[k/2] k−[k/2] ​小数。如果 n u m s 1 [ k / 2 − 1 ] ≤ n u m s 2 [ k / 2 − 1 ] nums1[k/2−1]≤nums2[k/2−1] nums1[k/2−1]≤nums2[k/2−1] ，同理可说明 n u m s 1 nums1 nums1 中的前 k / 2 k/2 k/2 个元素一定都小于等于第 k k k 小数，类似可将问题的规模减少一半.

现在，我们考虑边界情况。如果 m < k / 2 m

如果 n u m s 1 [ m − 1 ] > n u m s 2 [ k / 2 − 1 ] nums1[m−1]>nums2[k/2−1] nums1[m−1]>nums2[k/2−1] ，则 n u m s 2 nums2 nums2 中的前 k / 2 k/2 k/2 个元素一定都小于等于第 k k k 小数，我们可以将问题归约成在剩下的数中找第 k − ⌊ k / 2 ⌋ k−⌊k/2⌋ k−⌊k/2⌋ 小数.如果 n u m s 1 [ m − 1 ] ≤ n u m s 2 [ k / 2 − 1 ] nums1[m−1]≤nums2[k/2−1] nums1[m−1]≤nums2[k/2−1] ，则 n u m s 1 nums1 nums1 中的所有元素一定都小于等于第 k k k 小数，因此第 k k k小数是 n u m s 2 [ k − m − 1 ] nums2[k−m−1] nums2[k−m−1].

话不多说，上代码。代码里细节点很多，建议自己看懂后复写一遍。

class Solution {
public:
    double findMedianSortedArrays(vector &nums1, vector &nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0) {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        } else
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
    }

    int findKthNumber(vector &nums1, int i, vector &nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int si = min(int(nums1.size()), i + k / 2), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        else
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
    }
};