在n个项的数组中找到k个最小数的算法

Question

我正在尝试编写一种算法，可以在O（n）的时间内将n个最小的数字打印在n个大小的数组中，但是我无法将时间复杂度降低到n。我怎样才能做到这一点？

Answer 1

我之前在采访中已经做到了，最优雅/最有效的方法之一是O(n log k). with space: O(k) (thanks, @Nzbuu)基本上，您将使用大小限制为k的最大堆。对于数组中的每个项目，请检查其是否小于最大值（仅O（1））。如果是，则将其放入堆（O（log k））并删除最大值。如果更大，请转到下一个项目。当然，堆不会产生k个项目的排序列表，但是可以在O（k log k）中完成，这很容易。同样，对于找到最大的k个项目，您可以执行相同的操作，在这种情况下，您将使用最小堆。

Answer 2

对此问题的最佳解决方案如下：使用快速排序找到轴，并丢弃该第k个元素所在的部分，然后递归地找到下一个轴。（这是kth Max finder，您需要更改if else条件使其成为kth Min Finder）。这是JavaScript代码-&nbsp; // Complexity is O(n log(n))&nbsp; var source = [9, 2, 7, 11, 1, 3, 14, 22];&nbsp; var kthMax = function(minInd, MaxInd, kth) {&nbsp; &nbsp; &nbsp; // pivotInd stores the pivot position&nbsp;&nbsp; &nbsp; &nbsp; // for current iteration&nbsp; &nbsp; &nbsp; var temp, pivotInd = minInd;&nbsp; &nbsp; &nbsp; if (minInd >= MaxInd) {&nbsp; &nbsp; &nbsp; &nbsp; return source[pivotInd];&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; for (var i = minInd; i < MaxInd; i++) {&nbsp; &nbsp; &nbsp; &nbsp; //If an element is greater than chosen pivot (i.e. last element)&nbsp; &nbsp; &nbsp; &nbsp; //Swap it with pivotPointer element. then increase ponter&nbsp; &nbsp; &nbsp; &nbsp; if (source[i] > source[MaxInd]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp = source[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; source[i] = source[pivotInd];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; source[pivotInd] = temp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pivotInd++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; // we have found position for pivot elem.&nbsp;&nbsp; &nbsp; &nbsp; // swap it to that position place .&nbsp; &nbsp; &nbsp; temp = source[pivotInd];&nbsp; &nbsp; &nbsp; source[pivotInd] = source[MaxInd];&nbsp; &nbsp; &nbsp; source[MaxInd] = temp;&nbsp; &nbsp; &nbsp; // Only try to sort the part in which kth index lies.&nbsp; &nbsp; &nbsp; if (kth > pivotInd) {&nbsp; &nbsp; &nbsp; &nbsp; return kthMax(pivotInd + 1, MaxInd, kth);&nbsp; &nbsp; &nbsp; } else if (kth < pivotInd) {&nbsp; &nbsp; &nbsp; &nbsp; return kthMax(minInd, pivotInd - 1, kth);&nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return source[pivotInd];&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // last argument is kth-1 , so if give 2 it will give you,&nbsp; &nbsp; // 3rd max which is 11&nbsp; console.log(kthMax(0, source.length - 1, 2));