Skip to content

Instantly share code, notes, and snippets.

@bluesunxu
Last active December 10, 2015 01:48
Show Gist options
  • Save bluesunxu/4362189 to your computer and use it in GitHub Desktop.
Save bluesunxu/4362189 to your computer and use it in GitHub Desktop.
Find kth smallest element under O(k)
int findKthElem(int arr1[], int m, int arr2[], int n, int k)
{
assert(k>0 && k<=(m+n));
int i=0, j=0;
while(true)
{
if(i==m)
return arr2[j+k-1];
if(j==n)
return arr1[i+k-1];
if(arr1[i] < arr2[j]) {
if(k-- == 0)
return arr1[i];
++i;
}
else {
if(k-- == 0)
return arrr2[i];
++j;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment