Lexi's Leetcode solutions

[onsite] 找两个排好序的数组中的第k大的数

Posted on: August 24, 2013

private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}

private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: