Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit76b7c5f

Browse files
authored
Merge pull requestMisterBooo#86 from freetreer/master
0004_Solved
2 parents58d4e87 +74f1537 commit76b7c5f

File tree

8 files changed

+205
-0
lines changed

8 files changed

+205
-0
lines changed
3.93 MB
Loading
8.56 KB
Loading
8.88 KB
Loading
8.7 KB
Loading
16.7 KB
Loading
11.5 KB
Loading
Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
#LeetCode 第 4 号问题：寻找两个正序数组的中位数
2+
3+
>本文首发于公众号「图解面试算法」，是[图解 LeetCode](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
4+
>
5+
>同步博客：https://www.algomooc.com
6+
7+
题目来源于 LeetCode 上第 4 号问题：寻找两个正序数组的中位数。题目难度为 Hard，目前通过率为 29.0% 。
8+
9+
####题目描述
10+
11+
>给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
12+
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
13+
你可以假设 nums1 和 nums2 不会同时为空。
14+
15+
```java
16+
示例1：
17+
nums1= [1,3]
18+
nums2= [2]
19+
20+
则中位数是2.0
21+
22+
示例2：
23+
nums1= [1,2]
24+
nums2= [3,4]
25+
26+
则中位数是 (2+3)/2=2.5
27+
```
28+
29+
####题目解析
30+
这道题网络上的解析都非常“高深”，很难理解。私以为它们都将简单的问题复杂化了。本题在一些处理上确实会有些麻烦，比如数组边界的处理，和偶数个数的中位数的处理。但其核心思想并不复杂。
31+
32+
首先，我们可以只考虑数字总个数为奇数的情况。让我们看下下图：
33+
34+
![](../Animation/image1.PNG)
35+
36+
蓝框是中位数左边的数（包括中位数），而橘框则为中位数右边的数。
37+
38+
3个显然的规则：
39+
1.两个数组的蓝框总个数=(数字总个数+1)/2;
40+
2.所有蓝框内的数都小于橘框内的数
41+
3.中位数为蓝框中最大的那一位（即数组1蓝框最后一位，或数组2蓝框最后一位）
42+
![](../Animation/image2.PNG)
43+
如图，我们要找到一组A，B，满足上面3条规则。
44+
对于规则1，我们在数组1中找任意A，然后根据规则1就能推算出对应的B的位置。
45+
对于规则2，由于数组1和2都是有序数组，即X1<A<Y1;X2<B<Y2。我们实际上只需要判断A是否小于Y2，以及B是否小于Y2。
46+
对于规则3，由于数组1和2都是有序数组，因此中位数为A,B中较大的那一项。
47+
48+
那么具体该如何操作呢?
49+
由于数组1和2都是有序数组，且题目要求O(log(m+n))复杂度，我们明显应考虑二分法。
50+
51+
**情况1：**
52+
53+
![](../Animation/case1.png)
54+
55+
首先，我们选择数组1进行操作。取其中间值9 。（因此 A=9) 根据规则1,我们在数组2中找到对应值（B = 4）。（一共有11个数，(11+1) / 2 = 6，因此蓝色框总数为6）
56+
紧接着，我们根据规则2判断A(9)是否小于B.next(5)，以及B(4)是否小于A.next(11)。
57+
显然，A比B.next,也就是一个橘框还要大。这是不允许的。可见A只能取比9更小的数字了。如果取更大的数字，那B就会更小，更不可能满足规则2。所以这种情况下我们要向左进行二分。
58+
59+
**情况2：**
60+
61+
![](../Animation/case2.png)
62+
63+
这种情况下B比A.next,也就是一个橘框还要大。这是不允许的。可见A只能取比9更大的数字了。如果取更小的数字，那B就会更大，更不可能满足规则2。所以这种情况下我们要向右进行二分。
64+
65+
**情况3：**
66+
67+
![](../Animation/case3.png)
68+
69+
随着我们不断地二分，中位数显然必然会出现。
70+
如图上这种情况，A小于B.next，且B小于A.next。
71+
那么，显然，A,B中较大的那一项就是中位数（规则3）。
72+
73+
本题算法的核心思想就是这样简单。此外，当数字总数为偶数时，我们需要把我们求得的“中位数"与它下一项相加并除以2即可。由于本题中数字可能相同，所以大小的比较需要使用>=和<=。
74+
下面提供了作者的一份代码，leetcode上的结果为：执行用时：2 ms；内存消耗：40.3 MB，都超过了100%的用户。读者可以参考一下。
75+
76+
77+
####代码实现
78+
79+
Java语言
80+
81+
```java
82+
publicclassSolution {
83+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
84+
// 使nums1成为较短数组,不仅可以提高检索速度,同时可以避免一些边界问题
85+
if (nums1.length> nums2.length) {
86+
int[] temp= nums1;
87+
nums1= nums2;
88+
nums2= temp;
89+
}
90+
91+
int len1= nums1.length;
92+
int len2= nums2.length;
93+
int leftLen= (len1+ len2+1)/2;//两数组合并&排序后,左半边的长度
94+
95+
// 对数组1进行二分检索
96+
int start=0;
97+
int end= len1;
98+
while (start<= end) {
99+
// 两个数组的被测数A,B的位置(从1开始计算)
100+
// count1 = 2 表示 num1 数组的第2个数字
101+
// 比index大1
102+
int count1= start+ ((end- start)/2);
103+
int count2= leftLen- count1;
104+
105+
if (count1>0&& nums1[count1-1]> nums2[count2]) {
106+
// A比B的next还要大
107+
end= count1-1;
108+
}elseif (count1< len1&& nums2[count2-1]> nums1[count1]) {
109+
// B比A的next还要大
110+
start= count1+1;
111+
}else {
112+
// 获取中位数
113+
int result= (count1==0)? nums2[count2-1]:// 当num1数组的数都在总数组右边
114+
(count2==0)? nums1[count1-1]:// 当num2数组的数都在总数组右边
115+
Math.max(nums1[count1-1], nums2[count2-1]);// 比较A,B
116+
if (isOdd(len1+ len2)) {
117+
return result;
118+
}
119+
120+
// 处理偶数个数的情况
121+
int nextValue= (count1== len1)? nums2[count2]:
122+
(count2== len2)? nums1[count1]:
123+
Math.min(nums1[count1], nums2[count2]);
124+
return (result+ nextValue)/2.0;
125+
}
126+
}
127+
128+
returnInteger.MIN_VALUE;// 绝对到不了这里
129+
}
130+
131+
// 奇数返回true,偶数返回false
132+
privatebooleanisOdd(intx) {
133+
return (x&1)==1;
134+
}
135+
}
136+
```
137+
138+
####动画理解
139+
140+
![](../Animation/Animation.gif)
141+
142+
####复杂度分析
143+
144+
+ 时间复杂度：对数组进行二分查找，因此为O(logN)
145+
+ 空间复杂度：O(1)
146+
147+
148+
149+
150+
151+
![](../../Pictures/qrcode.jpg)
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
publicclassSolution {
2+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
3+
// 使nums1成为较短数组,不仅可以提高检索速度,同时可以避免一些边界问题
4+
if (nums1.length >nums2.length) {
5+
int[]temp =nums1;
6+
nums1 =nums2;
7+
nums2 =temp;
8+
}
9+
10+
intlen1 =nums1.length;
11+
intlen2 =nums2.length;
12+
intleftLen = (len1 +len2 +1) /2;//两数组合并&排序后,左半边的长度
13+
14+
// 对数组1进行二分检索
15+
intstart =0;
16+
intend =len1;
17+
while (start <=end) {
18+
// 两个数组的被测数A,B的位置(从1开始计算)
19+
// count1 = 2 表示 num1 数组的第2个数字
20+
// 比index大1
21+
intcount1 =start + ((end -start) /2);
22+
intcount2 =leftLen -count1;
23+
24+
if (count1 >0 &&nums1[count1 -1] >nums2[count2]) {
25+
// A比B的next还要大
26+
end =count1 -1;
27+
}elseif (count1 <len1 &&nums2[count2 -1] >nums1[count1]) {
28+
// B比A的next还要大
29+
start =count1 +1;
30+
}else {
31+
// 获取中位数
32+
intresult = (count1 ==0)?nums2[count2 -1]:// 当num1数组的数都在总数组右边
33+
(count2 ==0)?nums1[count1 -1]:// 当num2数组的数都在总数组右边
34+
Math.max(nums1[count1 -1],nums2[count2 -1]);// 比较A,B
35+
if (isOdd(len1 +len2)) {
36+
returnresult;
37+
}
38+
39+
// 处理偶数个数的情况
40+
intnextValue = (count1 ==len1) ?nums2[count2]:
41+
(count2 ==len2) ?nums1[count1]:
42+
Math.min(nums1[count1],nums2[count2]);
43+
return (result +nextValue) /2.0;
44+
}
45+
}
46+
47+
returnInteger.MIN_VALUE;// 绝对到不了这里
48+
}
49+
50+
// 奇数返回true,偶数返回false
51+
privatebooleanisOdd(intx) {
52+
return (x &1) ==1;
53+
}
54+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp