Finding K closest elements from the median of an unsorted Array

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.

1 answer

  • answered 2017-11-13 10:01 SaiBot

    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 Min Heap (of size k), where elements are organized according to distance to the median, in order to find the k nearest elements.

    The above should have a runtime of O(N log(k)) which is linear in N.