在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代码-

  // Complexity is O(n log(n))

  var source = [9, 2, 7, 11, 1, 3, 14, 22];

  var kthMax = function(minInd, MaxInd, kth) {

      // pivotInd stores the pivot position 

      // for current iteration

      var temp, pivotInd = minInd;

      if (minInd >= MaxInd) {

        return source[pivotInd];

      }

      for (var i = minInd; i < MaxInd; i++) {

        //If an element is greater than chosen pivot (i.e. last element)

        //Swap it with pivotPointer element. then increase ponter

        if (source[i] > source[MaxInd]) {

          temp = source[i];

          source[i] = source[pivotInd];

          source[pivotInd] = temp;

          pivotInd++;

        }

      }

      // we have found position for pivot elem. 

      // swap it to that position place .

      temp = source[pivotInd];

      source[pivotInd] = source[MaxInd];

      source[MaxInd] = temp;

      // Only try to sort the part in which kth index lies.

      if (kth > pivotInd) {

        return kthMax(pivotInd + 1, MaxInd, kth);

      } else if (kth < pivotInd) {

        return kthMax(minInd, pivotInd - 1, kth);

      } else {

        return source[pivotInd];

      }

    }

    // last argument is kth-1 , so if give 2 it will give you,

    // 3rd max which is 11

  console.log(kthMax(0, source.length - 1, 2));