如何在O(n)中找到长度为n的无序数组中的第k大元素?

我相信有一种方法可以找到长度为n的O(n)无序数组中第k大的元素。也可能是期望O(n)之类的。我们该怎么做呢?

当前回答

我想提出一个答案

如果我们取前k个元素并将它们排序成一个k个值的链表

对于每一个其他的值，即使在最坏的情况下如果我们对剩下的n-k个值进行插入排序即使在最坏的情况下，比较的数量也将是k*(n-k)对于前k个要排序的值让它是k*(k-1)所以结果是(nk-k)也就是o(n)

干杯

2009-07-31 16:51:47

其他回答

还有Wirth的选择算法，它的实现比QuickSelect简单。Wirth的选择算法比QuickSelect慢，但经过一些改进，它变得更快。

更详细地说。使用Vladimir Zabrodsky的MODIFIND优化和3中位数的枢轴选择，并注意算法划分部分的最后步骤，我提出了以下算法(想象一下，命名为“LefSelect”):

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

在我这里做的基准测试中，LefSelect比QuickSelect快20-30%。

2014-11-03 23:15:27

我想提出一个答案

如果我们取前k个元素并将它们排序成一个k个值的链表

干杯

2009-07-31 16:51:47

对于k非常小的值(即k << n)，我们可以在~O(n)时间内完成。否则，如果k与n比较，我们得到O(nlogn)

2012-10-05 05:21:15

这种方法怎么样

保持一个长度为k的缓冲区和一个tmp_max，得到tmp_max为O(k)并执行n次因此类似于O(kn)

是这样还是我漏掉了什么?

虽然它没有击败快速选择的平均情况和中值统计方法的最坏情况，但它非常容易理解和实现。