Find kthsmallest element from two sorted arrays
algorithm, arrays, sorting
Solution
Here's `O(log a.length + log b.length)` algorithm from the answer to "How to find the kth smallest element in the union of two sorted arrays?" question. It is a direct port from C++ recursive implementation to Java:
public static int ksmallest(int[] a, int[] b,
int a1, int a2, int b1, int b2,
int k) {
int lena = a2 - a1;
int lenb = b2 - b1;
assert (0 <= k && k < (lena + lenb));
if (lena == 0) {
return b[b1 + k];
}
if (lenb == 0) {
return a[a1 + k];
}
int mida = lena / 2;
int midb = lenb / 2;
int ma = a[a1 + mida];
int mb = b[b1 + midb];
if ((mida + midb) < k) {
return (mb < ma) ?
ksmallest(a, b, a1, a2, b1 + midb + 1, b2, k - (midb + 1)) :
ksmallest(a, b, a1 + mida + 1, a2, b1, b2, k - (mida + 1));
}
else {
return (mb < ma) ?
ksmallest(a, b, a1, a1 + mida, b1, b2, k) :
ksmallest(a, b, a1, a2, b1, b1 + midb, k);
}
}
There is also C++ iterative implementation with the same time complexity (without recursion). It could be ported to Java the same way as the recursive version.
Sanity check for the recursive version:
/** concatenate a, b arrays */
public static int[] concatenate(int[] a, int[] b) {
int lena = a.length;
int lenb = b.length;
int[] c = new int[lena + lenb];
System.arraycopy(a, 0, c, 0, lena);
System.arraycopy(b, 0, c, lena, lenb);
return c;
}
public static void main(String[] args) {
int a[] = {0, 3, 7, 8};
int b[] = {0, 2, 3};
int c[] = concatenate(a, b);
Arrays.sort(c);
for (int n = 0; n < (a.length + b.length); n++) {
int k = ksmallest(a, b, 0, a.length, 0, b.length, n);
if (k != c[n]) {
System.out.println(n + ": expected " + c[n] + " got " + k);
}
}
}
On success, it prints nothing.
Problem
I have implemented a working function that does it. But it is not very efficient because it copies a new copy in each call. I am having trouble converting it to using only a_start, a_end, b_start, b_end. I have tried a couple of ways to convert it, but none of them are working for all cases. How can I convert it so that it takes in a start and end pointers for both array a and b? I have tried the following and modified k-i-1 and k-j-1 so that it only takes in k, but did not work. ``` int m = a_right-a_left, n=b_right-b_left; int i = (a_left+a_right)/2; or int i = (int)((m* (k-1)) / (m+n) ); ``` Below is my working code using a new copy of array each call. ``` public static int kthSmallest(int[] a, int[] b, int k) { if (a.length==0) return b[k-1]; else if (b.length==0) return a[k-1]; else if (b.length<a.length) return kthSmallest(b, a, k); // make sure i + j = k - 1 int m = a.length, n=b.length; int i = (int)((double)m / (m+n) * (k-1)); // make sure i won't be out of bounds int j = k - 1 - i; int bj_1 = 0, ai_1 = 0; if (i==0) { ai_1 = Integer.MIN_VALUE; } // in case i = 0, outOfBound else { ai_1 = a[i-1]; } if (j==0) { bj_1 = Integer.MIN_VALUE; } // in case j = 0, outOfBound else { bj_1 = b[j-1]; } if (bj_1 < a[i] && a[i] < b[j]) // kth smallest found, b[j-1] < a[i] < b[j] return a[i]; if (ai_1 < b[j] && b[j] < a[i]) // kth smallest found, a[i-1] < b[j] < a[i] return b[j]; if ( a[i] < b[j] ) // if true, exclude a's lower bound (if 2 arrays merged, a's lower bound must // reside before kth smallest, so also update k. // also exclude b's upper bound, since they are all greater than kth element. return kthSmallest(Arrays.copyOfRange(a, i+1, a.length), Arrays.copyOfRange(b, 0, j), k-i-1); else return kthSmallest(Arrays.copyOfRange(a, 0, i), Arrays.copyOfRange(b, j+1, b.length), k-j-1); } ```