-
Notifications
You must be signed in to change notification settings - Fork 199
/
FindMedianSortedArrays.java
executable file
·108 lines (88 loc) · 3.4 KB
/
FindMedianSortedArrays.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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package Algorithms.array;
public class FindMedianSortedArrays {
public static void main(String[] strs) {
int A[] = {1, 2};
int B[] = {1, 2};
System.out.println(findMedianSortedArrays(A, B));
}
public static double findMedianSortedArrays1(int A[], int B[]) {
if (A == null || B == null) {
return 0;
}
int len = A.length + B.length;
double ret = 0;
// 偶数个元素
if (len % 2 == 0) {
ret = (findKth(A, B, 0, 0, len / 2) + findKth(A, B, 0, 0, len / 2 + 1)) / (double)2.0;
} else {
// 奇数个元素
ret = findKth(A, B, 0, 0, len / 2 + 1);
}
return ret;
}
// Find the Kth large number.
public static int findKth(int A[], int B[], int indexA, int indexB, int k) {
int lenA = A.length;
int lenB = B.length;
if (indexA >= lenA) {
return B[indexB + k - 1];
} else if (indexB >= lenB) {
return A[indexA + k - 1];
}
// Base Case, pay attention. 在这里必须要退出。因为k = 1的时候,不可能再分了。
if (k == 1) {
return Math.min(A[indexA], B[indexB]);
}
// -1是因为索引本身是从0开始的。而前k大元素含有k个元素。
int mid = k / 2 - 1;
// 注意,越界条件是 >= lenA. 怎么老是犯这个错误。。
int keyA = indexA + mid >= lenA ? Integer.MAX_VALUE: A[indexA + mid];
int keyB = indexB + mid >= lenB ? Integer.MAX_VALUE: B[indexB + mid];
// 因为丢弃了k / 2个元素
int kNew = k - k / 2;
if (keyA < keyB) {
return findKth(A, B, indexA + k / 2, indexB, kNew);
} else {
return findKth(A, B, indexA, indexB + k / 2, kNew);
}
}
public static double findMedianSortedArrays(int A[], int B[]) {
//2257
if (A == null || B == null) {
return 0;
}
int len = A.length + B.length;
if (len % 2 == 0) {
return (double)(dfs(A, B, 0, 0, len / 2) + dfs(A, B, 0, 0, len / 2 + 1)) / 2.0;
} else {
return dfs(A, B, 0, 0, len / 2 + 1);
}
}
public static double dfs(int A[], int B[], int aStart, int bStart, int k) {
if (aStart >= A.length) {
return B[bStart + k - 1];
} else if (bStart >= B.length) {
return A[aStart + k - 1];
}
if (k == 1) {
return Math.min(A[aStart], B[bStart]);
}
// k = 4;
// mid = 1;
int mid = k / 2 - 1;
if (aStart + mid >= A.length) {
// drop the left side of B.
return dfs(A, B, aStart, bStart + k / 2, k - k / 2);
} else if (bStart + mid >= B.length) {
// drop the left side of A.
return dfs(A, B, aStart + k / 2, bStart, k - k / 2);
} else if (A[aStart + mid] > B[bStart + mid]) {
// drop the left side of B.
return dfs(A, B, aStart, bStart + k / 2, k - k / 2);
} else if (A[aStart + mid] < B[bStart + mid]) {
// drop the left side of A.
return dfs(A, B, aStart + k / 2, bStart, k - k / 2);
}
return A[aStart + mid];
}
}