未分类长度为n的数组中k个最大元素的索引

Question

我需要找到未排序的，长度为n的数组/矢量在C++中k个最大元素的索引，其中k < n。我已经看到如何使用nth_element（）来查找第k个统计量，但我不确定使用这个是否是我的问题的正确选择，因为看起来我需要对nth_statistic进行k次调用，我猜测它会有复杂性O（kn），可能会达到它的最佳状态？或者有没有办法在O（n）中做到这一点？

在没有使用nth_element（）的情况下实现它看起来好像我必须遍历整个数组一次，填充每个步骤中最大元素的索引列表。

标准C++库中是否有任何东西使得这是一种单线或任何聪明的方式来实现这一点，我自己在几行？在我的具体情况中，k = 3，n = 6，所以效率不是一个大问题，但找到一个干净而有效的方法来为任意k和n做这件事是很好的。

它看起来像Mark the top N elements of an unsorted array可能是我可以找到的最接近的帖子，所发布的内容有Python和PHP。

Answer 1

您可以使用快速排序算法的基础来执行您所需的操作，除了重新排序分区外，您可以摆脱掉期望范围内的条目。

它被称为 “快速选择” 和here is a C++ implementation：

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; 
} 

OUTPUT：

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

编辑

这个特定的实现有一个O（n）的平均运行时间;由于选择主键的方法，它共享快速排序的最坏情况运行时间。通过optimizing the pivot choice，你最坏的情况也会变成O（n）。

Answer 2

标准库不会为您提供索引列表（它旨在避免传递冗余数据）。但是，如果你有兴趣在n个最大元素，使用某种类型的分区（包括std::partition和std::nth_element是为O（n））：

#include <iostream> 
#include <algorithm> 
#include <vector> 

struct Pred { 
    Pred(int nth) : nth(nth) {}; 
    bool operator()(int k) { return k >= nth; } 
    int nth; 
}; 

int main() { 

    int n = 4; 
    std::vector<int> v = {5, 12, 27, 9, 4, 7, 2, 1, 8, 13, 1}; 

    // Moves the nth element to the nth from the end position. 
    std::nth_element(v.begin(), v.end() - n, v.end()); 

    // Reorders the range, so that the first n elements would be >= nth. 
    std::partition(v.begin(), v.end(), Pred(*(v.end() - n))); 

    for (auto it = v.begin(); it != v.end(); ++it) 
     std::cout << *it << " "; 
    std::cout << "\n"; 

    return 0; 
} 

Answer 3

这是我的实现，我想要做什么，我认为是合理的有效：

#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 4

问题具有部分答案;即std::nth_element返回“第n个统计量”，其性质为前面第n个元素中的任何一个都大于它和后面的元素都不会少于。

因此，只需要一个电话到std::nth_element就足以得到k个最大的元素。时间复杂度将为O（n），理论上它是最小的，因为您必须至少访问每个元素一次才能找到最小（或最小k个）元素。如果您需要订购这些k元素，那么您需要对它们进行排序，这将是O（k log（k））。所以，总共O（n + k log（k））。

Answer 5

这应该是其在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; 
    } 
} 

Answer 6

执行代替@hazelnusse的改进版本

可以在这样做O(n)单次订单统计计算时间：

• 让r是k个顺序统计
• 初始化两个空列表bigger和equal。
• 对于每个索引i：
  • 如果array[i] > r，添加i到bigger
  • 如果array[i] = r，添加从equali到equal
• 丢弃元素，直到这两个列表的长度的总和是k
• 返回两个列表的连接。

当然，如果所有项目都不同，则只需要一个列表。如果需要，你可以做技巧将两个列表合并为一个，尽管这会使代码更复杂。

Answer 7

尽管以下代码可能无法满足所需的复杂性约束，但它可能是上述优先级队列的有趣替代方案。

#include <queue> 
#include <vector> 
#include <iostream> 
#include <iterator> 
#include <algorithm> 

std::vector<int> largestIndices(const std::vector<double>& values, int k) { 
    std::vector<int> ret; 

    std::vector<std::pair<double, int>> q; 
    int index = -1; 
    std::transform(values.begin(), values.end(), std::back_inserter(q), [&](double val) {return std::make_pair(val, ++index); }); 
    auto functor = [](const std::pair<double, int>& a, const std::pair<double, int>& b) { return b.first > a.first; }; 
    std::make_heap(q.begin(), q.end(), functor); 
    for (auto i = 0; i < k && i<values.size(); i++) { 
     std::pop_heap(q.begin(), q.end(), functor); 
     ret.push_back(q.back().second); 
     q.pop_back(); 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<double> values = { 7,6,3,4,5,2,1,0 }; 
    auto ret=largestIndices(values, 4); 
    std::copy(ret.begin(), ret.end(), std::ostream_iterator<int>(std::cout, "\n")); 
}