问从未排序数组的中值中寻找K个最近的元素

EN

我对此的建议是分两步进行。

首先，使用中间值算法在线性时间内求出未排序阵列的中值。

其次，扫描数组并填充(大小为k)的最大堆，其中元素按照与中位数的距离排列，以便找到k个最近的元素。

您可以确保堆以下列方式永远不包含超过k个元素。当您想要将(k+1)th元素添加到堆中时，可以检查它是否小于根元素。如果是这样，则将其添加到堆中，并在堆重组后移除(新的)根。如果没有，你可以放弃它。

上面的运行时应该是O(N log(k))，在N中是线性的。