-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKthElementInTwoSortedArray.java
More file actions
55 lines (40 loc) · 1.33 KB
/
Copy pathKthElementInTwoSortedArray.java
File metadata and controls
55 lines (40 loc) · 1.33 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
// Given two sorted arrays A, B of size m and n respectively.
// Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.
public class KthElementInTwoSortedArray {
public static void main(String[] arg) throws Exception{
int[] A = {0,2,4,6,8};
int [] B = {1,3,5,7};
for(int i = 1; i<=9; i++){
System.out.print(getKthElement(A,B,i));
}
}
public static int getKthElement(int[] A, int[] B, int k) throws Exception{
if(A.length + B.length < k) {
throw new Exception ("invalid input");
}
int s = k <= B.length ? 0 : k-B.length-1 ;
int e = k - 1 >= A.length ? A.length-1 : k-1;
// int s = 0;
// int e = A.length-1;
return getKthElementHelper(A,B,k,s,e);
}
public static int getKthElementHelper(int[] A, int[] B, int k, int s, int e){
if(s>e){
return getKthElementHelper(B,A, k, k <= A.length ? 0 : k-A.length-1, k - 1 >= B.length ? B.length-1 : k-1);
}
int m = (s+e) / 2;
int left = k - m -2;
int right = k - m - 1;
int low = (left< 0) ? Integer.MIN_VALUE : B[left];
int high = (right > B.length-1) ? Integer.MAX_VALUE : B[right];
if(A[m] >= low && A[m] <= high) {
return A[m];
}
else if (A[m] > high){
return getKthElementHelper(A,B,k,s,m-1);
}
else {
return getKthElementHelper(A,B,k,m+1,e);
}
}
}