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

Revision en1, by Cerberus14, 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


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