Hi Dave, Can you kindly eloborate your algorithm? How can we modify a single array in O(n) time, such that the median comes to become the n/2th element and smaller elements comes to the left side and larger elements comes to the right side? Kindly explain in detail.
2008/4/22 Pramod Negi <[EMAIL PROTECTED]>: > i didnt get what u want to so say (the bold lines) > > On 4/21/08, Dave <[EMAIL PROTECTED]> wrote: > > > > > Use a divide-and-conquer algorithm to find the median, rearranging the > > array so that the values less than the median precede it in the array > > and the values greater than the median follow it. So the median is a(n/ > > 2).* Now use the divide-and-conquer algorithm twice more to locate the > > (n/2-k)th and (n/2+k)th elements*. Finally, march out both directions > > from n/2, selecting the closest elements to a(n/2). Each of these > > operations can be done in O(n), so the total algorithm is O(n). > > > > Dave > > > > On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote: > > > hi this is prob 9-3.7 of CLRS , anybody having a clue??? > > > > > > Describe an O(n)-time algorithm that, given a set S of n distinct > > > numbers and a positive > > > integer k ≤ n, determines the k numbers in S that are closest to the > > > median of S > > > > > > thanks in advance.. > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
