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

Question

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

arraysalgorithmselection

36

我正在尝试编写一个算法，以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

14个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nisetama · Answer 1

这在k与n相比较小时，接近O(n)，当数组中有重复元素时也适用。

a=[1,1,13,8,10,5,17,1,2,12,3,15,7,16,14,20,18,19,4,9,6,11]
k=5
n=a.length

outmax=NaN
out=[]

for(i=0;i<n;i++){
  if(i<k||a[i]<outmax){
    insertat=k-1
    for(j=0;j<k-1;j++)if(a[i]<out[j]||j==i){insertat=j;break}
    for(j=k-1;j>insertat;j--)out[j]=out[j-1]
    out[insertat]=a[i]
    outmax=out[k-1]
  }
}

console.log(out)

- Tamer Shlash · Answer 2

只需使用归并排序对数组进行排序，然后打印前k个数字，最坏情况下需要n*log2(n)的时间。

- Matthew · Answer 3

使用堆来存储值如何？当您遍历数组中的每个值时，这个成本是n。

然后通过堆获取最小的k个值。

运行时间为O(n) + O(k) = O(n)

当然，现在内存空间为O(n + n)

- Sakib malik · Answer 4

这是递归基本条件的轻微变化，在选择算法中，返回指向包含所有前k个最小元素的动态数组的指针，随机顺序，时间复杂度为O(n)。

void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *A, int left, int right){
int pivot = A[right], i = left, x;

for (x = left; x < right; x++){
    if (A[x] < pivot){
        swap(&A[i], &A[x]);
        i++;
    }
}

swap(&A[i], &A[right]);
return i;
}


 int* quickselect(int *A, int left, int right, int k){

//p is position of pivot in the partitioned array
int p = partition(A, left, right);

//k equals pivot got lucky
if (p == k-1){
    int*temp = malloc((k)*sizeof(int));
    for(int i=left;i<=k-1;++i){
        temp[i]=A[i];
    }
    return temp;
}
//k less than pivot
else if (k - 1 < p){
    return quickselect(A, left, p - 1, k);
}
//k greater than pivot
else{
    return quickselect(A, p + 1, right, k);
}

}