using selection algorithm ... http://en.wikipedia.org/wiki/Selection_algorithm
On Jan 24, 3:15 am, Anand <anandut2...@gmail.com> wrote: > How to find K smallest using O(n) > > On Sun, Jan 23, 2011 at 9:33 AM, Dave <dave_and_da...@juno.com> wrote: > > @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 <riteshcseit...@gmail.com> 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 <learner....@gmail.com> 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
