leetcode|困难:4. 寻找两个正序数组的中位数

jupiter
2022-06-08 / 0 评论 / 621 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年06月08日,已超过849天没有更新,若内容或图片失效,请留言反馈。

1.题目

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1:

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

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • $-10^6$ <= nums1[i], nums2[i] <= $10^6$

2. 题解

2.1 思路分析

思路1:
    确定中位数的组成部分midLeft和midRight,总数为奇数的midLeft=midRight
    通过利用寻找第k小的数的算法来锁定midLeft和midRight

寻找第k小的数算法

由于数列是有序的,其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数,我们可以每次循环排除掉 k/2 个数。看下边一个例子。

假设我们要找第 7 小的数字。

image.png

我们比较两个数组的第 k/2 个数字,如果 k 是奇数,向下取整。也就是比较第 3 个数字,上边数组中的 4 和下边数组中的 3,如果哪个小,就表明该数组的前 k/2 个数字都不是第 k 小数字,所以可以排除。也就是 1,2,3 这三个数字不可能是第 7 小的数字,我们可以把它排除掉。将 1349和 45678910 两个数组作为新的数组进行比较。

更一般的情况 A[1]A[2]A[3]A[k/2] ... ,B[1]B[2]B[3]B[k/2] ... ,如果 A[k/2]<B[k/2] ,那么A[1]A[2]A[3]A[k/2]都不可能是第 k 小的数字。

A 数组中比 A[k/2] 小的数有 k/2-1 个,B 数组中,B[k/2]A[k/2] 小,假设 B[k/2] 前边的数字都比 A[k/2] 小,也只有 k/2-1 个,所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个,所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了,所以可以把它们排除。

橙色的部分表示已经去掉的数字。

image.png

由于我们已经排除掉了 3 个数字,就是这 3 个数字一定在最前边,所以在两个新数组中,我们只需要找第 7 - 3 = 4 小的数字就可以了,也就是 k = 4。此时两个数组,比较第 2 个数字,3 < 5,所以我们可以把小的那个数组中的 1 ,3 排除掉了。

image.png

我们又排除掉 2 个数字,所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数,4 == 4,怎么办呢?由于两个数相等,所以我们无论去掉哪个数组中的都行,因为去掉 1 个总会保留 1 个的,所以没有影响。为了统一,我们就假设 4 > 4 吧,所以此时将下边的 4 去掉。

image.png

由于又去掉 1 个数字,此时我们要找第 1 小的数字,所以只需判断两个数组中第一个数字哪个小就可以了,也就是 4。

所以第 7 小的数字是 4。

我们每次都是取 k/2 的数进行比较,有时候可能会遇到数组长度小于 k/2的时候。

image.png

此时 k / 2 等于 3,而上边的数组长度是 2,我们此时将箭头指向它的末尾就可以了。这样的话,由于 2 < 3,所以就会导致上边的数组 1,2 都被排除。造成下边的情况。

image.png

由于 2 个元素被排除,所以此时 k = 5,又由于上边的数组已经空了,我们只需要返回下边的数组的第 5 个数字就可以了。

从上边可以看到,无论是找第奇数个还是第偶数个数字,对我们的算法并没有影响,而且在算法进行中,k 的值都有可能从奇数变为偶数,最终都会变为 1 或者由于一个数组空了,直接返回结果。

所以我们采用递归的思路,为了防止数组长度小于 k/2,所以每次比较 min(k/2len(数组) 对应的数字,把小的那个对应的数组的数字排除,将两个新数组进入递归,并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。

2.2 代码实现

  • 思路1:利用第k小的数来寻找中位数
class Solution {
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1; // 计算数组1的剩余部分的长度
        int len2 = end2 - start2 + 1; // 计算数组2的剩余部分的长度

        // 递归出口
        // 让 len1 的长度小于 len2,这样就能保证如果有数组空了,一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        // 当其中一个数组都消耗完
        if (len1 == 0) return nums2[start2 + k - 1];
        // k=1的边界情况
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        // 迁移探索k/2
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        // 缩小探索空间
        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;

        // 计算中位数的位置
        int midLeftIndex = (nums1Len + nums2Len -1) / 2;
        int midRightIndex = (nums1Len + nums2Len) / 2;

        // 用寻找第k小的数的算法来找到 中位数的midLeft 和 midRight
        int midLeft = getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, midLeftIndex+1);
        int midRight = getKth(nums1, 0, nums1Len - 1, nums2, 0, nums2Len - 1, midRightIndex+1);

        // 计算中位数
        double res = (midLeft+midRight) * 0.5;

        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1,2};
        int[] nums2 = {4};

        Double res =solution.findMedianSortedArrays(nums1,nums2);
        System.out.println(res);
    }
}

2.3 提交结果

提交结果执行用时内存消耗语言提交时间备注
通过1 ms42.4 MBJava2022/06/08 21:12添加备注

参考资料

  1. https://leetcode.cn/problems/median-of-two-sorted-arrays
  2. https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
0

评论 (0)

打卡
取消