Given two sorted arrays return the Kth largest. int KthLargestofTwoSortedArrays(int *arr1, int size1, int *arr2, int size2, int k)
{
if (k < 1 || k > size1 + size2)
throw "Bad k input!";
// Optimization - If both arrays form a large sorted array when put next to eachother
if (arr1[size1 - 1] < arr2[0])
{
if (k <= size1)
return arr1[k - 1];
else
return arr2[k - size1 - 1];
}
if (arr2[size2 - 1] < arr1[0])
{
if (k <= size2)
return arr2[k - 1];
else
return arr1[k - size2 - 1];
}
// Similar mechanism to the merge part of Merge-Sort
int i1 = 0, i2 = 0, count = 0, ret = 0;
while (i1 < size1 || i2 < size2)
{
if (i1 < size1 && arr1[i1] < arr2[i2])
ret = arr1[i1++];
else
ret = arr2[i2++];
count++;
if (k == count)
return ret;
}
} |