Given an unsorted array, I am trying to find the K nearest elements to the median of an Array. I am having trouble finding the solution in linear running time.
A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34 # assume sorting part is done
Median here is 6.
Answer for this is 2,3,4,5,6.
Any help or hint will be appreciated.
My suggestion for this would be a two step approach.
First, use the Median of Medians algorithm to find the Median of an unsorted array in linear time.
Second, scan the array and fill a Max Heap (of size k), where elements are organized according to distance to the median, in order to find the k nearest elements.
You ensure that the heap never contains more than k elements in the following way. When you want add the (k+1)th element to the heap you check if it is smaller than the root. If so you add it to the heap, and after reorganization of the heap you remove the (new)root. If not you can discard it.
The above should have a runtime of O(N log(k)) which is linear in N.
assume sorting part is done? If it should run in linear time, how can we assume that? Is it allowed to use additional data structures? - Duarte Meneses