2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Changing to |a-median| will transform like that. But how will that yield k closest to the median. I am looking for an O(n) solution $\endgroup$
    – daniel
    Nov 17, 2021 at 21:26
  • $\begingroup$ okay, so once you have the kth smallest value, you can find all the numbers less than it in a single iteration $\endgroup$
    – daniel
    Nov 17, 2021 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.