6

按顺序查找数组中 k 个最大元素的最快方法是什么（即从最大元素开始到第 k 个最大元素）？

4

7 回答 7

12

一种选择如下：

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

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

步骤 (1) 花费时间 O(n)，步骤 (2) 花费时间 O(k log k)。总体而言，该算法运行时间为 O(n + k log k)，非常非常快。

希望这可以帮助！

于 2013-01-22T01:16:45.550 回答
1

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) 时间。

于 2013-01-22T01:26:39.470 回答
1

基数排序解决方案：

  • 对数组进行降序排序，使用基数排序；
  • 打印前 K 个元素。

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

但是，我认为基数排序的开销很大，这使得它的线性时间复杂度不那么有吸引力。

于 2015-01-03T05:49:01.650 回答
1

1) 在 O(n) 中构建一个 Max Heap 树
2) 使用 Extract Max k 次从 Max Heap O(klogn) 中获取 k 个最大元素

时间复杂度：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;
}
于 2017-08-21T17:53:52.967 回答
0

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

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

于 2013-01-22T01:25:01.680 回答
0

这是一个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并RandomizedSelet在此 github 源文件中定义。

于 2018-06-13T01:02:32.320 回答
0

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

为前 3 个值创建一个值类。使用这样的累加器来减少并行流。根据上下文（内存、功率）限制并行度。

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();
}
于 2019-02-19T14:09:23.390 回答