First find the median of the array in O(n) time using *'Linear general
selection algorithm - "Median of Medians algorithm" '* (
http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22)
by finding (n+1)/2 smallest element (for odd n). You can also refer Pg 189,
Introduction of Algorithms , II edition (Cormen) for the algorithm.
Then apply the same algorithm to partition the array by locating the (k+1)th
smallest element. In the corresponding partition function instead of
directly comparing the values at two indexes use a compare function which
compares modulus of difference of the element and the median found ie
int compare (int a, int b, int median){
return ( abs(median - a) - abs(median - b)) ;
}
Overall time complexity : O(n), space complexity : O(1).
On Sun, Aug 30, 2009 at 8:36 PM, Dufus <rahul.dev.si...@gmail.com> wrote:
>
> Is it acceptable if I
> find the median in O(logn) time and then,
>
Can you elaborate how can we find the median of an unsorted array in O(log
n) time?
> find k numbers closest to the median in O(k) space and O(n) time?
>
> _dufus
>
>
> On Aug 30, 4:38 pm, Nagendra Kumar <nagendra....@gmail.com> wrote:
> > Given a set S of n distinct numbers and a positive integer k <= n.
> > Determine the k numbers in S that are closest to the median of S.
> > Find an O(n) algorithm
>
> >
>
--
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 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
-~----------~----~----~----~------~----~------~--~---
