找出按顺序排列的k个最大元素

Question

如何以最快的方式按顺序查找数组中的前k个最大元素（即从第一个最大元素开始到第k个最大元素）？

- user1742188

---

你能假设数组没有重复元素吗？还是必须考虑这种情况？ - templatetypedef

我们必须考虑到这种情况。 - user1742188

Answer 1

以下是一种方案：

1. 使用线性时间的选择算法，如中位数或内省排序，找到第k大的元素，并重新排列元素，使得从第k个元素向后的所有元素都大于第k个元素。

2. 使用快速排序算法（如堆排序或快速排序）对第k个元素向后的所有元素进行排序。

步骤（1）的时间复杂度为O(n)，步骤（2）的时间复杂度为O(k log k)。总体而言，该算法的时间复杂度为O(n + k log k)，非常非常快。

希望这能帮到您！

- templatetypedef

---

非常好的方法。也许你想添加一些关于存在重复项和特别是第k大的并列情况的说明。（这不是改变游戏规则，但值得考虑。） - hardmath

@hardmath，实际上对算法没有任何影响。 - rici

@hardmath- 如果可能存在重复元素，我们可以使用哈希表将所有元素存储起来，并将唯一的元素重新写回数组中，以期望的 O(n) 时间解决该问题。然后你就可以使用这个相同的算法。 - templatetypedef

@hardmath：如果数组少于k个元素，那么它肯定不起作用，如果您想要非常挑剔的话。否则，我建议“查找k个最大元素”的区别是合理的俗语，特别是考虑到精确算法的链接，“查找k个大于或等于所有其余元素的元素”。 - rici

@templatetypedef，我认为“查找k个最大元素”和“查找k个最大值”之间存在语义差异。 - rici

Answer 2

1）在O（n）时间内构建一个最大堆树
2）使用“提取最大值”k次，从最大堆中获取k个最大元素，时间复杂度为O（klogn）

时间复杂度：O（n + klogn）

下面是使用STL的C++实现：

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

int main() {

  int arr[] = {4,3,7,12,23,1,8,5,9,2}; 

  //Lets extract 3 maximum elements
    int k = 3;  

    //First convert the array to a vector to use STL
    vector<int> vec;
    for(int i=0;i<10;i++){
        vec.push_back(arr[i]);
    }

  //Build heap in O(n)
  make_heap(vec.begin(), vec.end());

  //Extract max k times
  for(int i=0;i<k;i++){
      cout<<vec.front()<<" ";
      pop_heap(vec.begin(),vec.end());
      vec.pop_back();
  }
  return 0;
}

- chauprin

Answer 3

C++还提供了partial_sort算法，它解决了选择最小的k个元素（已排序）的问题，时间复杂度为O(n log k)。由于这应该通过反转排序谓词来完成，因此没有提供选择最大的k个元素的算法。

对于Perl，CPAN提供了Sort::Key::Top模块，它提供了一组函数，使用多个排序和自定义键提取过程从列表中选择前n个元素。此外，Statistics::CaseResampling模块提供了一个使用快速选择计算分位数的函数。

Python的标准库（自2.4以来）包括heapq.nsmallest()和nlargest()，返回排序后的列表，前者的时间复杂度为O(n + k log n)，后者的时间复杂度为O(n log k)。

- Raghavan

Answer 4

基数排序解决方案：

• 使用基数排序将数组按降序排序；
• 打印前K个元素。

时间复杂度：O(N*L)，其中L = 最大元素的长度，可以假设L = O(1)。 空间使用：基数排序需要O(N)的空间。

然而，我认为基数排序有昂贵的开销，使得其线性时间复杂度不太具有吸引力。

- ninhnn

Answer 5

这是一个时间复杂度为O(N + k lg k)的解决方案。

int[] kLargest_Dremio(int[] A, int k) {
  int[] result = new int[k];
  shouldGetIndex = true;
  int q = AreIndicesValid(0, A.Length - 1) ? RandomizedSelet(0, A.Length-1,
    A.Length-k+1) : -1;
  Array.Copy(A, q, result, 0, k);
  Array.Sort(result, (a, b) => { return a>b; });
  return result;
} 

AreIndicesValid 和 RandomizedSelect 在这个 GitHub 源代码文件中被定义。

- Atiq Rahman

Answer 6

有一个关于性能和受限资源的问题。

为前三个值创建一个值类。在并行流中使用这样的累加器进行规约。根据上下文（内存、功率）限制并行性。

class BronzeSilverGold {
    int[] values = new int[] {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};

    // For reduction
    void add(int x) {
        ...
    }

     // For combining two results of two threads.
    void merge(BronzeSilverGold other) {
        ...
    }
}

在您的程序中必须限制并行性，因此请在以下位置指定N_THREADS：

try {
    ForkJoinPool threadPool = new ForkJoinPool(N_THREADS);
    threadPool.submit(() -> {
        BronzeSilverGold result = IntStream.of(...).parallel().collect(
            BronzeSilverGold::new,
            (bsg, n) -> BronzeSilverGold::add,
            (bsg1, bsg2) -> bsg1.merge(bsg2));
        ...
    });
} catch (InterruptedException | ExecutionException e) {
    prrtl();
}

- Joop Eggen

Answer 7

@templatetypedef的解决方案可能是最快的，假设您可以修改或复制输入。

另外，您可以使用堆或BST（在C++中使用set）来存储给定时刻的k个最大元素，然后逐个读取数组的元素。虽然这是O(n lg k)，但它不会修改输入，并且仅使用O(k)的额外内存。它还适用于流（当您不知道从一开始就有所有数据时）。

- rburny