未排序长度n数组中k个最大元素的索引

Question

我需要在C++中找到未排序的长度为n的数组/向量的k个最大元素的索引,其中k <n.我已经看到如何使用nth_element()来查找第k个统计量,但是我不确定使用它是否是我的问题的正确选择,因为我似乎需要对nth_statistic进行k调用,我猜它会有复杂度O(kn),它可能会得到它的好处吗？或者有没有办法在O(n)中做到这一点？

在没有nth_element()的情况下实现它似乎我将不得不迭代整个数组一次,在每一步填充最大元素的索引列表.

标准C++库中是否有任何内容可以使它成为一个单行或任何巧妙的方法来自己实现这几行？在我的特殊情况下,k = 3,n = 6,因此效率不是一个大问题,但找到一个干净有效的方法来为任意k和n做这个很好.

看起来Mark未排序数组的前N个元素可能是我在SO上找到的最接近的帖子,其中的帖子有Python和PHP.

Answer 1

这是我的实现,做我想要的,我认为是合理有效的:

#include <queue>
#include <vector>
// maxindices.cc
// compile with:
// g++ -std=c++11 maxindices.cc -o maxindices
int main()
{
  std::vector<double> test = {0.2, 1.0, 0.01, 3.0, 0.002, -1.0, -20};
  std::priority_queue<std::pair<double, int>> q;
  for (int i = 0; i < test.size(); ++i) {
    q.push(std::pair<double, int>(test[i], i));
  }
  int k = 3; // number of indices we need
  for (int i = 0; i < k; ++i) {
    int ki = q.top().second;
    std::cout << "index[" << i << "] = " << ki << std::endl;
    q.pop();
  }
}

给出输出:

index[0] = 3
index[1] = 1
index[2] = 0

Answer 2

这应该是@hazelnusse的改进版本,它的执行O(nlogk)代替O(nlogn)

#include <queue>
#include <iostream>
#include <vector>
// maxindices.cc
// compile with:
// g++ -std=c++11 maxindices.cc -o maxindices
int main()
{
  std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4};
  std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q;
    int k = 5; // number of indices we need
  for (int i = 0; i < test.size(); ++i) {
    if(q.size()<k)
        q.push(std::pair<double, int>(test[i], i));
    else if(q.top().first < test[i]){
        q.pop();
        q.push(std::pair<double, int>(test[i], i));
    }
  }
  k = q.size();
  std::vector<int> res(k);
  for (int i = 0; i < k; ++i) {
    res[k - i - 1] = q.top().second;
    q.pop();
  }
  for (int i = 0; i < k; ++i) {
    std::cout<< res[i] <<std::endl;
  }
}

8 4 1 2 6

Answer 3

这个问题有部分答案; 即std::nth_element返回"的第n个统计量"与该属性没有第n个前的元素是比它更大,并且没有一个元素的下列它是更少.

因此,只需一次调用即可std::nth_element获得k个最大的元素.时间复杂度将是O(n),理论上它是最小的,因为你必须至少一次访问每个元素以找到最小(或在这种情况下是k-最小)元素.如果您需要订购这些k元素,那么您需要订购它们为O(k log(k)).所以,总共O(n + k log(k)).

Answer 4

您可以使用快速排序算法的基础来完成您需要的操作，除了无需重新排序分区之外，您还可以删除超出所需范围的条目。

它被称为“快速选择”，下面是一个 C++ 实现：

int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r ) {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

int quick_select(int* input, int p, int r, int k)
{
    if ( p == r ) return input[p];
    int j = partition(input, p, r);
    int length = j - p + 1;
    if ( length == k ) return input[j];
    else if ( k < length ) return quick_select(input, p, j - 1, k);
    else  return quick_select(input, j + 1, r, k - length);
}

int main()
{
    int A1[] = { 100, 400, 300, 500, 200 };
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl;
    int A2[] = { 100, 400, 300, 500, 200 };
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl;
    int A3[] = { 100, 400, 300, 500, 200 };
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl;
    int A4[] = { 100, 400, 300, 500, 200 };
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl;
    int A5[] = { 100, 400, 300, 500, 200 };
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl;
}

输出：

1st order element 100
2nd order element 200
3rd order element 300
4th order element 400
5th order element 500

编辑

该特定实现的平均运行时间为 O(n)；由于选择主元的方法，它与快速排序具有相同的最坏情况运行时间。通过优化主元选择，最坏的情况也变为 O(n)。