How do I find k closest integers in an array to its median?

Revision en1, by rezzaque, 2017-03-20 14:58:49

The array A is not sorted and has n distinct integer elements. Our aim to find k<=n elements that are closest to the median of this array. The distance is in terms of absolute value of the element and median's difference. The algorithm asked must have O(n) complexity.

Tags linear time, partition, selections

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rezzaque 2017-03-20 14:58:49 328 Initial revision (published)