algorithm - 从未排序数组的中位数中查找 K 个最接近的元素

Question

给定一个未排序的数组，我试图找到距离数组中位数最近的 K 个元素。我无法在线性运行时间内找到解决方案。

A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34    # assume sorting part is done

这里的中位数是 6。

答案是 2,3,4,5,6。

任何帮助或提示将不胜感激。

Answer 1

我对此的建议是分两步走。

首先，使用 Median of Medians在线性时间内找到未排序数组的中位数的算法。

其次，扫描数组并填充一个Max Heap (大小为 k)，其中元素根据到中位数的距离进行组织，以便找到 k 个最近的元素。

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

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