MelodyJerry
2021/07/29阅读:88主题:自定义主题1
4. 找两个正序数组的中位数
4. 找两个正序数组的中位数
难度 | 困难 | 通过率 | 40.49% (458209/1131417) |
---|
给定两个大小分别为 m
和 n
的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的 中位数
。
示例 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
示例 3:
输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
示例 4:
输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
-
nums1.length
==m
-
nums2.length
==n
-
0 <= m
<= 1000 -
0 <= n
<= 1000 -
1 <= m
+n
<= 2000 -
<= nums1[i]
,nums2[i]
<=
进阶:
你能设计一个时间复杂度为 的算法解决此问题吗?
✔题解
① 归并查找
如果忽略进阶中的时间复杂度要求为 的话,是很快速、容易地解决地。
一个比较直观的做法:将两个数组合并,排序,然后分别取得 total / 2
和 (total - 1) / 2
两个位置的数,取两者平均值。
这样做的目的是为了避免分情况讨论:合并后的数组长度是奇数还是偶数。
时间复杂度:合并两个数组的复杂度是 ,对合并数组进行排序的复杂度是 。整体复杂度是 。
空间复杂度: 。
② 分割线+二分查找
使用二分法直接在两个数组中找中位数分割线,使得nums1
和nums2
中分割线满足以下性质即可根据分割线左右的数来确定中位数:
-
假设
m = nums1.length
,n = nums2.length
-
确保数组 nums1
的长度
一定是不大于nums2
的-
若大于,则交换即可: -
递归 findMedianSortedArrays(nums2, nums1)
-
-
设 i
为nums1
中分割线,则取值为[0, m]
,表示分割线左侧元素下标为[0, i-1]
,分割线右侧元素下标为[i, m-1]
;设j
为nums2
中分割线,则取值为[0, n]
,表示分割线左侧元素下标为[0, j-1]
,分割线右侧元素下标为[i, n-1]
。
-
-
为确保
分割线左边个数要比右边个数多1
,需要进行一个细节处理,m+n
会有两种情况:-
正常下: -
m+n
为偶数:i + j = (m + n)/2
(5+5)/2=5 -
m+n
为奇数:i + j = (m + n)/2
(除以2是向下取整
) (4+5)/2=4
-
-
统一后: -
m+n
为偶数:i + j = (m + n + 1)/2
(5+5+1)/2=5 -
m+n
为奇数:i + j = (m + n + 1)/2
(现变为向上取整
) (4+5+1)/2=5
-
-
-
分割线左侧元素
小于等于
分割线右侧元素。由于两个数组均为正序数组,则只需要要求:nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
-
由于上该条件等价于在
[0, m]
中找到最大的i
使得nums1[i-1] <= nums2[j]
,因此可以使用二分查找。-
因为 i+j=(m+n+1)/2
,所以只要确定i
,就能确定j
了-
j=(m+n+1)/2-i
-
-
证明:假设我们已经找到了满足条件的 最大i
,使得nums1[i-1] <= nums2[j]
,那么此时必有nums[i] > nums2[j]
,进而有nums[i] > nums2[j-1]
-
-
分割线找到后,若
m+n
为奇数
,分割线左侧
的最大值
即为中位数;若为偶数
,分割线左侧
的最大值
与分割线右侧
的最小值
的平均数
即为中位数。 -
时间复杂度:
O(log(m, n))
,空间复杂度:O(1)
。
上述只是简单的描述,详细需要移步到下面的两种题解,我也是参考他们的题解来解决的,配合下面的视频。
推荐第1个题解,我的思路和他差不多,最关键是人家录了视频哈哈!
分割+二分+分治
视频题解:LeetCode004-两个有序数组的中位数-最优算法代码讲解[1]
作者:up主 甩手掌柜凡三岁[2]

分割线+二分查找
视频题解:4. 寻找两个正序数组的中位数[3]
文字题解:二分查找定位短数组的「分割线」(Java )[4]
作者:李威威同学[5]
③ 从两个有序数组中找第 k 小的数
无意间发现三叶姐的题解,和其他题解有些不一样
来源:宫水三叶的思辨日记
首先可以将原问题等效为:从两个有序数组中找第 k 小的数
。
分两种情况讨论:
-
总个数为偶数:找到 第 (total / 2) 个小的数
和第 (total / 2 + 1) 个小的数
,结果为两者的平均值。 -
总个数为奇数:结果为 第 (total / 2 + 1) 个小的数
。
具体思路为:
-
默认第一个数组比第二个数组的有效长度短,如果不满足,则调换两个数组(这也是一个常用技巧,目的是减少边界处理工作:原本需要对两个数组做越界检查,现在只需要对短的数组做越界检查) -
第一个数组的有效长度从 i
开始,第二个数组的有效长度从j
开始,其中[i,si - 1]
是第一个数组的前k / 2
个元素,[j,sj - 1]
是第二个数组的前k - k / 2
个元素(为了确保 k 为奇数的时候正确) -
当 nums1[si - 1] > nums2[sj - 1]
:则表示第k
小一定不在[j,sj - 1]
中,即在[i,n]
或[sj,m]
中 -
当 nums1[si - 1] <= nums2[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);
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]) {
return find(n1, i, n2, sj, k - (sj - j));
} else {
return find(n1, si, n2, j, k - (si - i));
}
}
}
}
时间复杂度:每次递归 k 的规模都减少一半,复杂度为
空间复杂度:
参考资料
LeetCode004-两个有序数组的中位数-最优算法代码讲解: https://www.bilibili.com/video/BV1H5411c7oC?from=search&seid=5223709810640990198
[2]甩手掌柜凡三岁: https://www.bilibili.com/video/BV1H5411c7oC?from=search&seid=5223709810640990198
[3]4. 寻找两个正序数组的中位数: https://www.bilibili.com/video/BV1Xv411z76J
[4]二分查找定位短数组的「分割线」(Java ): https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/
[5]李威威: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/
作者介绍