寻找n个元素数组中k个最小数的算法

Question

我正在尝试编写一个算法，以O(n)的时间打印n大小数组中最小的k个数字，但我无法将时间复杂度降至n。我该如何做到这一点？

我试图编写一个O(n)时间复杂度的算法来打印n大小数组中最小的k个数字，但我无法在时间复杂度为n的情况下实现。请问有什么方法可以解决这个问题吗？

- Jessica

---

我认为有必要澄清一下。您是否正在寻找N个数字数组中最小的K个数字？ - Jerry Coffin

不操作，那就是练习中已经写好的所有解释了......我想我必须显示数组中的所有k个小数.... :( - Jessica

@Jessica 这里有一个类似的问题：http://gateoverflow.in/27194/tifr2014-b-9 - Pranav

Answer 1

我曾在一次面试中做过这个问题，其中最优雅/高效的方法之一是

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

基本上，你将使用一个大小限制为k的最大堆。对于数组中的每个项目，检查它是否小于最大值（仅O(1)时间）。如果是，则删除最大值并将其放入堆中（O(log k)时间）。如果它更大，则继续下一个项目。

当然，堆不会产生排序后的k个项目列表，但这可以在O(k log k)的时间内完成，非常容易。

同样地，你也可以找到最大的k个项目，这时候你需要使用一个最小堆。

- Chet

---

这是我的做法。它也很容易实现，只需要 O(k) 的空间。 - Nzbuu

@Geek 堆被初始化为空，然后您想要迭代数组中的前k个项目来填充它。然后按照我描述的方式进行操作，您的代码将保持堆的大小恒定为k。堆是一种标准的树形数据结构，通常每个节点有两个子节点（参见：http://en.wikipedia.org/wiki/Heap_(data_structure)）。 - Chet

Blum等人的选择算法在最坏情况下需要O(n)时间和O(1)空间。即使你要报告排序后的项目，也可以在O(n + k log(k))时间/O(1)空间内完成。 - user1196549

@btilly：在实证中混合渐进界和“实际”考虑的参数是不可接受的。 - user1196549

在这种情况下，如果k和n的大小相当，则理论上正确的选择算法将更快。如果k比n小得多，并且您的数据存储在磁盘上，则理论上错误的堆算法将更快，而且速度会加倍。因此，从业者应该了解两种解决方案，并知道在优化很重要时使用哪种。 - btilly

Answer 2

您需要使用“选择算法”找到第k小的元素，该算法的时间复杂度为O(n)，然后再次迭代数组并返回每个小于等于该元素的元素。
选择算法: http://en.wikipedia.org/wiki/Selection_algorithm
如果有重复项，您需要注意确保不返回超过k个元素（例如，如果有1、2、...、k、k、k、...）。

编辑:
完整算法，并要求返回一个列表：假设数组为A。

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

请注意，如果你的列表可能有重复项，则需要第三次迭代。 如果没有重复项，则不需要进行第三次迭代，只需将4.1中的条件更改为<=。
还要注意：L.add将一个元素插入到链表中，因此是O(1)。

- amit

---

对于你的第五步骤，有一个小优化建议：5. while ( counter <= k ): 5.1 L.add(z); 5.2 counter <- counter + 1;。这将确保你不会再次遍历整个数组，因为你知道在第5步中添加到列表L的唯一元素是z，只需要进行（k-counter）次迭代而不是N次。 - srikanta

@srikfreak：我决定不进行这个优化，因为这显然是一个硬件问题，所以我想保持它简单易懂，避免添加条件。当将此算法实现到真正的软件中时，你当然是正确的，必须进行这个优化。 - amit

Answer 3

假设您正在尝试显示K个最小的数字，您可以使用Hoare's Select算法来查找第k个最小的数字。这将把数组分成较小的数字、第k个数字和较大的数字。

- Jerry Coffin

---

+1，但要注意Hoare的快速选择算法不是O(n)，它有糟糕的最坏情况。修正后的版本被称为“中位数法”，并且不是由Hoare发明的。 - Steve Jessop

Answer 4

能够在 O(n) 的时间内找到 n 个元素中的前 k 小数（我指的是真正的 O(n) 时间，而不是 O(n + 某个关于 k 的函数)）。请参考维基百科“选择算法”的“无序部分排序”和“中位数选择作为枢轴策略”的子部分，以及“中位数”的文章，了解使得这种算法达到 O(n) 的重要组成部分。

- David K

Answer 5

这可以在预期的线性时间(O(n))内完成。首先使用枢轴分区方法找到数组的第kth小元素(用于查找kth顺序统计量)，然后简单地迭代循环，检查哪些元素小于kth最小元素。请注意，这仅对不同的元素有效。

以下是C代码:

    /*find the k smallest elements of an array in O(n) time. Using the Kth order 
statistic-random pivoting algorithm to find the kth smallest element and then looping 
through the array to find the elements smaller than kth smallest element.Assuming 
distinct elements*/


    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    #define SIZE 10
    #define swap(X,Y) {int temp=X; X=Y; Y=temp;}


    int partition(int array[], int start, int end)
    {
        if(start==end)
            return start;
        if(start>end)
            return -1;
        int pos=end+1,j;
        for(j=start+1;j<=end;j++)
        {       
            if(array[j]<=array[start] && pos!=end+1)
            {
                swap(array[j],array[pos]);
                pos++;
            }
            else if(pos==end+1 && array[j]>array[start])
                pos=j;
        }
        pos--;
        swap(array[start], array[pos]);
        return pos;
    }

    int order_statistic(int array[], int start, int end, int k)
    {
        if(start>end || (end-start+1)<k)
            return -1;                   //return -1 
        int pivot=rand()%(end-start+1)+start, position, p;
        swap(array[pivot], array[start]);
        position=partition(array, start, end);
        p=position;
        position=position-start+1;                  //size of left partition
        if(k==position)
            return array[p];
        else if(k<position)
            return order_statistic(array, start,p-1,k);
        else
            return order_statistic(array,p+1,end,k-position);
    }


    void main()
    {
        srand((unsigned int)time(NULL));
        int i, array[SIZE],k;
        printf("Printing the array...\n");
        for(i=0;i<SIZE;i++)
            array[i]=abs(rand()%100), printf("%d ",array[i]);
        printf("\n\nk=");
        scanf("%d",&k);
        int k_small=order_statistic(array,0,SIZE-1,k);
        printf("\n\n");
        if(k_small==-1)
        {
            printf("Not possible\n");
            return ;
        }
        printf("\nk smallest elements...\n");
        for(i=0;i<SIZE;i++)
        {
            if(array[i]<=k_small)
                printf("%d ",array[i]);
        }
    }

- sudeepdino008

Answer 6

最佳解决方案如下。使用快速排序查找枢轴并丢弃不包含第k个元素的部分，并递归地查找下一个枢轴。(这是第k大的查找器，您需要更改if else条件以使其成为第k小的查找器)。以下是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));

- sapy

---

最坏情况下的快速排序是O(n*n)。 - paparazzo

是的，但是，在O(n log n)的最佳情况下，这是解决此问题的最佳方法。如果您选择合并或堆，则需要额外的O(n)内存，因此快速排序对于平均n log n排序解决方案而言是相当可接受的。 - sapy

Answer 7

另一种技术-使用QuickSelect算法，结果将是返回结果左侧的所有元素。平均时间复杂度为O(n)，最坏情况下为O(n^2)。空间复杂度为O(1)。

- Neel Shah

Answer 8

我不确定您具体需要什么，但以下方案时间复杂度为O(n * k)，空间复杂度为O(k)。这里的k是最大值，需要进行调整。

对于暴力求解中的k（结果），可以使用堆来替代。

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            result[indexMin] = testArray[i];
            min = result[indexMin];
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}

- paparazzo

Answer 9

我相信可以使用O(n)的时间和O(n)的空间来完成此操作。正如提到的，您可以使用Hoare算法或quickselect的变体。

基本上，您在数组上运行Quicksort，但仅在需要的分区一侧运行，以确保有K个或K-1个大于枢轴的元素（您可以包括或排除枢轴）。如果列表不需要排序，则可以从枢轴打印数组的余数。由于快速排序可以原地完成，因此需要O(n)空间，并且由于每次平均检查的数组部分减少了一半，所以需要O(2n)== O(n)时间

- Aaron Parry

Answer 10

如前所述，有两种方法可以完成这样的任务：

1）您可以使用快速排序、堆排序或任何您想要的O(n log n)排序算法对n个元素的整个数组进行排序，然后选择您数组中的m个最小值。这种方法将在O(n log n)的时间复杂度内运行。

2）您可以使用选择算法来查找您数组中的m个最小元素。找到kth最小值需要O(n)的时间，由于您将迭代此算法m次，因此总时间将为m x O(n) = O(n)。

- Mirac Suzgun