Describe an O(n)-time algorithm that, given a set S of n distinct numbers and a positive integer $k \leq n$, determines the k numbers in S that are closest to the median of S.
Assume for simplicity that n is odd and k is even. If the set S was in sorted order, the median is in position n=2 and the k numbers in S that closest to the median are in positions (n − k)/2 through (n + k)/2. We first use linear time selection to fi nd the (n − k)/2, n/2, and (n + k)/2 elements and then pass through the set S to fi nd the numbers less than (n+k)/2 element, greater than the (n−k)/2 element, and not equal to the n/2 element. The algorithm takes O(n) time as we use linear time selection exactly three times and traverse the n numbers in S once(Use for loop to do comparisons to find element > (n-k)/2 and less than (n+k)/2 but not equal to n/2 ).
No comments:
Post a Comment