-
Notifications
You must be signed in to change notification settings - Fork 1
/
MedianOfTwoSortedArrays.java
53 lines (49 loc) · 1.12 KB
/
MedianOfTwoSortedArrays.java
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
package leetcode;
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
int[] temp = A;
A = B;
B = temp;
int tmp = m;
m = n;
n = tmp;
}
int min = 0;
int max = m;
int halfLen = (m + n + 1) / 2;
while (min <= max) {
int i = (min + max) / 2;
int j = halfLen - i;
if (i < max && B[j - 1] > A[i]) {
min = i + 1;
} else if (i > min && A[i - 1] > B[j]) {
max = i - 1;
} else {
int maxLeft = 0;
if (i == 0) {
maxLeft = B[j - 1];
} else if (j == 0) {
maxLeft = A[i - 1];
} else {
maxLeft = (Math.max(B[j - 1], A[i - 1]));
}
if ((m + n) % 2 == 1) {
return maxLeft;
}
int minRight = 0;
if (i == m) {
minRight = B[j];
} else if (j == n) {
minRight = A[i];
} else {
minRight = Math.min(B[j], A[i]);
}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}