LC 4、寻找两个正序数组的中位数

题目描述

这是LeetCode 4、寻找两个正序数组的中位数，难度为 困难

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出并返回这两个正序数组的「中位数」。

示例：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

朴素解法

最简单，也是最容易想到的思路就是，将两个数组进行合并排序，然后分别进行分类讨论，如果合并数组长度为奇数，则返回total/2位置的数字，如果是偶数，我们就返回 total/2 和(total - 1) / 2 位置的数字，并取其平均值。

此处有一小trick，我们可以直接将奇偶看作一种情况处理，得到的结果是一样的，这样就能避免分类讨论。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int> ans(m + n);
        int i = 0;
        for(int n1 : nums1) ans[i++] = n1;
        for(int n2: nums2) ans[i++] = n2;
        sort(ans.begin(), ans.end());
        return (double(ans[ans.size() / 2]) + double(ans[(ans.size() - 1) / 2])) / 2;
    }
};

我们使用algorithm 中的sort函数进行排序，该排序算法时间复杂度为O(nlog(n))

• 时间复杂度：合并两个数组的复杂度是 O(m + n)，对合并数组进行排序的复杂度是 O(nlog(n))。整体复杂度是 O((m + n)log(m + n))
• 空间复杂度：O(m + n)

分治解法

首先可以将原问题等效为：从两个有序数组中找到第k小的数字。

1. 总数为奇数时：找到 第（total / 2）个小的数 和 第（total / 2 + 1）个小的数
2. 总数为偶数时：找到 第（total / 2 + 1）个小的数。

具体思路为：

• 默认第一个数组比第二个数组的有效长度短，如果不满足，则调换两个数组（这也是一个小trick，目的是减少边界处理工作；原本需要对两个数组做越界检查，现在只需要对短的数组做越界检查）
• 第一个数组的有效长度从 i 开始，第二个数组的有效长度从 j 开始，其中 【i， si - 1】 是第一个数组的前 k / 2 个元素，【i, sj - i】 是第二个数组的前 k - k / 2 个元素 （为了确保 k 为奇数的时候正确）
• 当 nums[si - 1] > nums[sj - 1] : 则表示第 k 小一定不在 【j, sj - 1】 中，即在 【i, n】 或者 【sj, m】 中 (如果不是这样子，凑不齐k个数字)
• 当 nums[si - 1] <= nums[sj - 1] : 则表示第 k 小一定不在 【i, si - 1】 中， 即在 【si, n】 或 【j, m】 中

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int tot = nums1.length + nums2.length;
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }
    int find(int[] n1, int i, int[] n2, int j, int k) {
        //要确保第一个数组比第二个短
        if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
        //如果当前已经将短的数组遍历完成了，说明一定不在短的数组里面，在长的数组里面，而且
        //这里 i >= n1.length 的意思是n1数组已经消耗殆尽，只有一个数组，那么就是n2[j + k - 1]
        if (i >= n1.length) return n2[j + k - 1];
        // 如果是找第一小的数组，直接返回两个数组的最小头即可
        if (k == 1) {
            return Math.min(n1[i], n2[j]);
        } else {
            int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
            if (n1[si - 1] > n2[sj - 1]) {
                // 我们就抛弃掉不符合要求的数组半边，但由于我们抛弃的半边其实是可以全部归结到小于第k个数的阵营去的
                // 所以我们只需要找k - 右半辣的数据的第k小的数字就行了
                return find(n1, i, n2, sj, k - (sj - j));
            } else {
                // 同理抛弃半边
                return find(n1, si, n2, j, k - (si - i));
            }
        }
    }
}

• 时间复杂度：每次递归 k 的规模都减少一般，复杂度为 O(log(m + n))
• 空间复杂度：O(1)

Label：二分，分治