友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
4. 寻找两个正序数组的中位数
给定两个大小分别为 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 -
-106 <= nums1[i], nums2[i] <= 106
思路分析
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2018-07-01
*/
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (isEmpty(nums1) && isEmpty(nums2)) {
return 0;
}
if (isEmpty(nums1)) {
return singleArray(nums2);
}
if (isEmpty(nums2)) {
return singleArray(nums1);
}
int length = nums1.length + nums2.length;
boolean isOdd = (length & 1) == 1;
int i1 = 0;
int i2 = 0;
int min = nums1[0] < nums2[0] ? nums1[0] : nums2[0];
int temp = min;
int last = min;
int now = min;
for (int i = 0; i < length; i++) {
if (i1 < nums1.length && i2 < nums2.length) {
if (nums1[i1] <= nums2[i2]) {
temp = nums1[i1];
i1++;
} else {
temp = nums2[i2];
i2++;
}
} else if (i1 < nums1.length) {
temp = nums1[i1];
i1++;
} else {
temp = nums2[i2];
i2++;
}
if (i > 0) {
last = now;
now = temp;
}
if (length / 2 == i) {
if (isOdd) {
return now;
} else {
return ((double) (last + now)) / 2.0;
}
}
}
return 0;
}
private static boolean isEmpty(int[] nums) {
return nums == null || nums.length == 0;
}
public static double findMedianSortedArraysBest(int[] nums1, int[] nums2) {
// TODO
return 0;
}
private static double singleArray(int[] nums2) {
boolean isOdd = (nums2.length & 1) == 1;
if (isOdd) {
return nums2[nums2.length / 2];
} else {
return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-12-06 22:50:37
*/
public double findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) {
int[] tmp = a;
a = b;
b = tmp;
}
int m = a.length;
int n = b.length;
// 循环不变量：a[left] <= b[j+1]
// 循环不变量：a[right] > b[j+1]
int left = -1;
int right = m;
while (left + 1 < right) { // 开区间 (left, right) 不为空
int i = left + (right - left) / 2;
int j = (m + n + 1) / 2 - i - 2;
if (a[i] < b[j + 1]) {
left = i; // 缩小二分区间（i, right）
} else {
right = i; // 缩小二分区间（left, i）
}
}
// 此时 left 等于 right - 1
// a[left] <= b[j+1] 且 a[right] > b[j'+1] = b[j]，所以答案是 i = left
int i = left;
int j = (m + n + 1) / 2 - i - 2;
int ai = i >= 0 ? a[i] : Integer.MIN_VALUE;
int bj = j >= 0 ? b[j] : Integer.MIN_VALUE;
int ai1 = i + 1 < m ? a[i + 1] : Integer.MAX_VALUE;
int bj1 = j + 1 < n ? b[j + 1] : Integer.MAX_VALUE;
int max1 = Math.max(ai, bj);
int min2 = Math.min(ai1, bj1);
return (m + n) % 2 > 0 ? max1 : (max1 + min2) / 2.0;
}