Tuesday, March 20, 2012

kth element in 2 unsorted arrays.


Given two unsorted int arrays, find the kth element in the merged, sorted array.
example:
int[] A= [3 1 7]
int[] B = [4 9]
k: 3
return 4.


Approach:
Since the arrays are unsorted, we can take first element of array A say X, 
Considering X as pivot we can divide array A as the number of elements that are less then X say a and number of elements greater than X say b
Similarly consider X as the pivot get the count of elements less than X in array B say c and elements greater than X in array B say d.
now if a+c == k then X is the kth element
if (k < a+c) then do the above steps again the subarrays A[0..a] and B[0..c] with k 
Otherwise do the above steps again the subarrays A[b ..n] and B[d..m] with k = (b+d)-k.

No comments:

Post a Comment