CODEWITHSUNDEEP
algorithmsorting
bbbBB
bbbBB

Reputation: 65

Find closest in value to the median of S

Given an unsorted array A[1....N], trying to find the K numbers in A that are closes in value to the median of A. I can find the median of A in linear time O(N). Can I also find K in linear time?? for example. A = [9,2,7,3,8,1,12}, Median(A) = 7, and 3 items with closes values to 7 are {7,8,9}.

Upvotes: 1

Views: 327

Answers (1)

Mark Borgerding
Mark Borgerding

Reputation: 8476

I think you want a selection algorithm such as Introselect. If you happen to be implementing in c++, you can use the very useful std::nth_element

It will rearrange a sequence of elements such that all elements before a given point are less than those elements that follow. Do this twice and you've got your set of K elements that are closest to the mean.

Upvotes: 2

Related Questions