@Ritesh: Very clever. In step 2 you should take the absolute value, meaning that you need a copy of the original array in order to recover the closest numbers, or in step 3 you should find the k smallest absolute values. It is more work, but still O(n), but then you don't need the extra copy of the array since you can just add the median back into the array.
Dave On Jan 23, 10:22 am, ritesh <[email protected]> wrote: > 1.) find x= median in o(n) > 2.) subtract x from each number of the array > 3.) find the k smallest number using o(n) algrithm > > On Jan 21, 4:04 am, snehal jain <[email protected]> wrote: > > > > > Given an unsorted array A of n distinct numbers and an integer k where > > 1 <= k <= n, design an algorithm that finds the k numbers in A that > > are closest in value to the median of A in O(n) time.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
