Nice :-) That doesnt even require O(k) extra space. _dufus
On Sep 1, 8:36 pm, Shishir Mittal <[email protected]> wrote: > @Nagendra : As earlier told Refer Pg 189, Cormen, an algorithm is given to > find the Kth largest element in O(n) *worst* time complexity. > > @Dufus: yeah, am pretty sure that the algorithm I have described results in > K closest elements to median. > For e.g. Let the array be 2 5 7 10 11 14 19 45 121 i.e. n= 9 elements and 5 > closest medians are required. > > First determine the median in O(n) time using Linear general selection > algorithm - "Median of Medians > algorithm"<http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selec...>by > looking for 5th largest element in the array. > Median = 11. > > int compare (int a, int b, int median){ > return ( abs(median - a) - abs(median - b)) ;} > > Rest of the task is similar to first finding the (k)th smallest element in > the array > |2-11|, |5-11|, |7-11|, |10-11|, |11-11|, |14-11|, |19-11|, | 45-11|, > |121-11| > i.e. 9, 6, 4, 1, 0, 3, 8, 34, 110 > and then partitioning the array around the pivot and returning the first k > elements as the solution. > Storing the above array in O(n) space and then performing the task would > have ease the task but if space is a constraint (constant space), compare > function described above can be used. > > Working for constant space, > Using the compare function, let ** the first recursive call SELECT(arr, 0, > 8, 5) *for e.g* does partitioning for index 2. > The partitioned array for pivot arr[2] = 7 is > (10, 11, 14) 7 (2, 5, 19, 45, 121) (order of elements in the bracket may > vary depending upon coding). > equivalent to (1, 0, 3,) 4 ( 9, 6, 8, 34, 110) for O(n) space case. > so 7 is the 4th smallest element. > > the above calls SELECT (arr, 4, 8, 5 - 4) > which *ultimately* partitions the array into > (10 , 11, 14, 7,) 5 (2, 19, 45, 121) > equivalent to (1, 0, 3, 4,) 6 ( 9, 8, 34, 110) for O(n) space case. > > the first 5 elements is the required answer. > > Overall worst case time complexity : O(n), space complexity : O(1). > O(n) space simplifies the coding and understanding of the problem. > > On Tue, Sep 1, 2009 at 6:04 PM, ankur aggarwal > <[email protected]>wrote: > > > @shishir > > > i could understand > > cann u give an example.. > > -- > Shishir Mittal > Ph: +91 9936 180 121 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
