Repository navigation
Expand file tree
/
Copy path_4.java
More file actions
104 lines (87 loc) · 3.98 KB
/
Copy path_4.java
File metadata and controls
104 lines (87 loc) · 3.98 KB
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
package com.fishercoder.solutions;
import static java.lang.Math.max;
import static java.lang.Math.min;
/**
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
*/
public class _4 {
class Solution1 {
/**credit: https://discuss.leetcode.com/topic/28602/concise-java-solution-based-on-binary-search
*
* The key point of this problem is to ignore half part of A and B each step recursively by comparing the median of remaining A and B:
if (aMid < bMid) Keep [aRight + bLeft]
else Keep [bRight + aLeft]
As the following: time=O(log(m + n))
*/
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length, n = B.length;
int l = (m + n + 1) / 2;
int r = (m + n + 2) / 2;
return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
}
public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
if (aStart > A.length - 1) return B[bStart + k - 1];
if (bStart > B.length - 1) return A[aStart + k - 1];
if (k == 1) return Math.min(A[aStart], B[bStart]);
int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1];
if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];
if (aMid < bMid)
return getkth(A, aStart + k/2, B, bStart, k - k/2);// Check: aRight + bLeft
else
return getkth(A, aStart, B, bStart + k/2, k - k/2);// Check: bRight + aLeft
}
}
class Solution2 {
/**
* Reference: https://leetcode.com/discuss/28843/my-accepted-java-solution:
* Basic Idea is very similar to K-selection. it's easier to understand if you imagine this to be chopping off the last K elements from a total of len(A) + len(B) elements,
* where K = (len(A) + len(B))/2.
* we want to remove K, but each time we can remove only at most K/2 elements,
* because we can only be sure that these elements are not within the first (len(A) + len(B)) -K elements.
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int K = nums1.length + nums2.length;
if (K % 2 == 0) {
return (findMedianSortedArrays(nums1, nums2, (K - K / 2)) + findMedianSortedArrays(nums1, nums2, (K - (K / 2 + 1)))) / 2;
} else {
return findMedianSortedArrays(nums1, nums2, K - (K / 2 + 1));
}
}
// k is the number of elements to REMOVE, or "Chop off"
public double findMedianSortedArrays(int A[], int B[], int K) {
int lowA = 0, lowB = 0;
int highA = A.length;
int highB = B.length;
int midA;
int midB;
while (K > 0 && highA > 0 && highB > 0) {
int chopA = max(1, min(K / 2, (highA) / 2));
int chopB = max(1, min(K / 2, (highB) / 2));
midA = highA - chopA;
midB = highB - chopB;
if (A[midA] < B[midB]) { // here A[0 .. midA] < B[midB], and we know that B[0 .. midB-1] < B[midB], so B[midB..highB] can not possibly be within the first (len(A) + len(B) - K) elements, and can be safely removed.
highB = midB;
K = K - chopB;
} else {
highA = midA;
K = K - chopA;
}
}
if (highA == 0 && highB == 0) return 0;
if (highA == 0) return B[highB - 1 - K];
if (highB == 0) return A[highA - 1 - K];
return max(A[highA - 1], B[highB - 1]);
}
}
}