未排序长度n数组中k个最大元素的索引 [英] indices of the k largest elements in an unsorted length n array

问题描述

我需要找到C ++中未排序的，长度为n的数组/向量的k个最大元素的索引，其中k <.我已经看到了如何使用nth_element()查找第k个统计信息，但是我不确定使用此方法是否是解决我的问题的正确选择，因为似乎我需要对nth_statistic进行k次调用，我猜它将具有复杂度O(kn)，这可能和它可以得到的一样好?还是仅在O(n)中有办法做到这一点?

I need to find the indices of the k largest elements of an unsorted, length n, array/vector in C++, with k < n. I have seen how to use nth_element() to find the k-th statistic, but I'm not sure if using this is the right choice for my problem as it seems like I would need to make k calls to nth_statistic, which I guess it would have complexity O(kn), which may be as good as it can get? Or is there a way to do this just in O(n)?

在没有nth_element()的情况下实现它似乎需要遍历整个数组一次，并在每一步中填充最大元素的索引列表.

Implementing it without nth_element() seems like I will have to iterate over the whole array once, populating a list of indices of the largest elements at each step.

标准C ++库中是否有任何东西可以使它成为单行代码，也可以通过任何聪明的方法仅用几行代码就可以自己实现?在我的特定情况下，k = 3，n = 6，因此效率并不是一个大问题，但是最好找到一种干净有效的方法来对任意k和n进行处理.

Is there anything in the standard C++ library that makes this a one-liner or any clever way to implement this myself in just a couple lines? In my particular case, k = 3, and n = 6, so efficiency isn't a huge concern, but it would be nice to find a clean and efficient way to do this for arbitrary k and n.

它看起来像标记未排序的前N个元素数组可能是我在SO上可以找到的最接近的帖子，其中的帖子在Python和PHP中.

It looks like Mark the top N elements of an unsorted array is probably the closest posting I can find on SO, the postings there are in Python and PHP.

推荐答案

以下是我的实现，可以实现我想要的效果，我认为这是相当有效的:

Here is my implementation that does what I want and I think is reasonably efficient:

#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

这篇关于未排序长度n数组中k个最大元素的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！