patternMinor
Find k closest numbers to the median
Viewed 0 times
findthenumbersclosestmedian
Problem
The formal problem statement is: Given a set S of n distinct numbers and a positive integer k<=n, determine the k numbers in S closest to the median.
My thoughts:
I have read about the median of median algorithm, which goes like group n elements in groups of 5 and finds the median of them and then recursively finds the median of the resulting array, which will have size n/5. This runs in O(n) time. So once we have the median, how to go about finding the k closest element to it, that seems to be another tricky thing.
My thoughts:
I have read about the median of median algorithm, which goes like group n elements in groups of 5 and finds the median of them and then recursively finds the median of the resulting array, which will have size n/5. This runs in O(n) time. So once we have the median, how to go about finding the k closest element to it, that seems to be another tricky thing.
Solution
Hint 1: try to transform the $n$ elements in such a way that the $k$ closest to the median will be the smallest $k$ elements after the transformation.
Hint 2: now use a standard algorithm to find the $k$'th smallest value (also known as the $k$'th order statistic). You might have learned an algorithm that computes this as a variation of the quickselect algorithm
Hint 2: now use a standard algorithm to find the $k$'th smallest value (also known as the $k$'th order statistic). You might have learned an algorithm that computes this as a variation of the quickselect algorithm
Context
StackExchange Computer Science Q#145854, answer score: 2
Revisions (0)
No revisions yet.