FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/code/lc4.java at master · mJackie/leetcode · GitHub
mJackie
/
leetcode
Public
Notifications
You must be signed in to change notification settings
Fork
135
Star
405
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
code
/
lc4.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
65 lines (60 loc) · 2.04 KB
Breadcrumbs
leetcode
/
code
/
lc4.java
Copy path
File metadata and controls
65 lines (60 loc) · 2.04 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package
code
;
/*
* 4. Median of Two Sorted Arrays
* 题意：两个有序数组，找出中位数，要求复杂度O(logN)
* 难度：Hard
* 分类：Array, Binary Search, Divide and Conquer
* 注意：两个数组长度可能不一样；边际问题
* 复杂度是 O(log(min(m,n)) ，在短的数组上二分查找即可
*/
public
class
lc4
{
public
static
void
main
(
String
[]
args
) {
int
[]
nums1
= {
1
,
2
};
int
[]
nums2
= {
3
,
4
};
System
.
out
.
println
(
findMedianSortedArrays
(
nums1
,
nums2
));
}
public
static
double
findMedianSortedArrays
(
int
[]
nums1
,
int
[]
nums2
) {
int
size1
=
nums1
.
length
;
int
size2
=
nums2
.
length
;
if
(
size1
>
size2
)
return
findMedianSortedArrays
(
nums2
,
nums1
);
int
low
=
0
;
int
high
=
nums1
.
length
;
while
(
low
<=
high
){
// <=别忘了=
int
i
= (
low
+
high
)/
2
;
int
j
= (
size1
+
size2
+
1
)/
2
-
i
;
// 注意+1
if
(
i
>
0
&&
nums1
[
i
-
1
]>
nums2
[
j
]){
//注意判断i是否越界
//need reduce i
high
=
i
-
1
;
}
else
if
(
i
<
size1
&&
nums2
[
j
-
1
]>
nums1
[
i
]){
//注意判断i是否越界
//need increase i
low
=
i
+
1
;
}
else
{
//find correct i
int
l
,
r
;
if
(
i
==
0
) {
//nums1 没有 l
l
=
nums2
[
j
-
1
];
}
else
if
(
j
==
0
){
//nums2 没有l，两个数组可能相等
l
=
nums1
[
i
-
1
];
}
else
{
l
=
Math
.
max
(
nums1
[
i
-
1
],
nums2
[
j
-
1
]);
}
if
((
size1
+
size2
)%
2
==
1
)
return
l
;
if
(
i
==
size1
){
//nums1 没有 r
r
=
nums2
[
j
];
}
else
if
(
j
==
size2
){
//nums2 没有 r
r
=
nums1
[
i
];
}
else
{
r
=
Math
.
min
(
nums1
[
i
],
nums2
[
j
]);
}
return
(
l
+
r
)*
1.0
/
2
;
}
}
return
-
1
;
}
}
Back
|
FazBrowse Home
|
New Git URL