给定一个未排序的数组，我试图找到距离数组中位数最近的 K 个元素。我无法在线性运行时间内找到解决方案。
A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34 # assume sorting part is done
这里的中位数是 6。
答案是 2,3,4,5,6。
任何帮助或提示将不胜感激。
最佳答案
我对此的建议是分两步走。
首先，使用Median of Medians在线性时间内找到未排序数组的中位数的算法。
其次，扫描数组并填充Max Heap (大小为 k)，其中元素根据到中位数的距离进行组织，以便找到 k 个最近的元素。
您可以通过以下方式确保堆中永远不会包含超过 k 个元素。当您想要将第 (k+1) 个元素添加到堆中时，您检查它是否小于根。如果是这样，您将其添加到堆中，并在重组堆后删除(新)根。如果没有，您可以丢弃它。
上面的运行时间应该是 O(N log(k))，与 N 成线性关系。
关于algorithm - 从未排序数组的中位数查找 K 个最接近的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47253561/