【刷题记录】4. 寻找两个正序数组的中位数

作者：WangNing

2022 年 7 月 08 日
本文字数：1371 字
阅读完需：约 4 分钟

一、题目描述

来源：力扣（LeetCode）

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

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

算法的时间复杂度应该为 $O (l o g (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
-106 <= nums1[i], nums2[i] <= 106

二、思考分析

1 简单暴力-合并数组求解中位数

直接合并两个有序数组，得到一个数组。然后直接得到中位数即可。这个可能是我们第一时间想到的方法。不考虑时间复杂度的话。
这种方法的时间复杂度为 $O (m + n)$ 不满足题目 $O (l o g (m + n))$ 的要求

2. 二分法

对于一个正序的数组，查找数组的中位数，实质上就是寻找数组中第 X 小的数组（X 就是中位数位于数组中的第几位），所以我们可以把这个问题转换为寻找第 X 个数。
对于两个正序数组来说，就是寻找两个数组中第 2/X 小的数组
然后比较两个数组的第 2/X 个数的大小
如果第一个数组 num1 的第 2/X 个数字小于于第二个数字的那么说明 num1 的前 2/X 个数组中不存在我们最终需要找的整体第 X/2 小的值，可以排除这些数
因为排除的数组肯定位于中位数前面然后在排除之外的两个新数组 X-排除的数小的即可
为了防止数组长度小于 X/2，所以每次比较 min(X/2，len(数组) 对应的数字，把小的那个对应的数组的数字排除，将两个新数组进入递归，并且 X 要减去排除的数字的个数。递归出口就是当 X=1 或者其中一个数字长度是 0 了。

三、代码实现

class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int n = nums1.length;        int m = nums2.length;        int x = n + m;
        if(x % 2 == 0){            int l = findnum(nums1, 0, n - 1, nums2, 0, m - 1, x/2 );            int r = findnum(nums1, 0, n - 1, nums2, 0, m - 1, x/2+1 );            return (l + r) / 2.0 ;        }
        return findnum(nums1, 0, n - 1, nums2, 0, m - 1, x/2+1);    }
    private int findnum(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int x) {        int len1 = end1 - start1 + 1;        int len2 = end2 - start2 + 1;        //为了好区别遍历 我们统一将num1当做短的数组        if (len1 > len2) return findnum(nums2, start2, end2, nums1, start1, end1, x);        if (len1 == 0) return nums2[start2 + x - 1];                if (x == 1) return Math.min(nums1[start1], nums2[start2]);
        int i = start1 + Math.min(len1, x / 2) - 1;        int j = start2 + Math.min(len2, x / 2) - 1;
        if (nums1[i] > nums2[j]) {            return findnum(nums1, start1, end1, nums2, j + 1, end2, x - (j - start2 + 1));        }        else {            return findnum(nums1, i + 1, end1, nums2, start2, end2, x - (i - start1 + 1));        }    }}

复制代码

复杂度分析

时间复杂度 $O (l o g (m + n))$

运行结果

总结

多思考问题的本质，然后将问题转为我们我们熟悉的思想。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/2c1f3dc1271b75125154df140】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景