c++ - 在向量中查找 n 个最大值

Question

我目前有一个向量，需要在其中找到 n 个最大的数字。例如，用户输入 5，我必须运行它并输出最大的 5。问题是，由于其他限制，我无法对该向量进行排序。解决这个问题的最佳方法是什么？

谢谢！

Answer 1

根据您对不修改原始向量的描述以及我认为您希望订单重要的假设，我建议std::partial_sort_copy：

//assume vector<int> as source
std::vector<int> dest(n); //largest n numbers; VLA or std::dynarray in C++14
std::partial_sort_copy(
    std::begin(source), std::end(source), //.begin/.end in C++98/C++03
    std::begin(dest), std::end(dest), 
    std::greater<int>() //remove "int" in C++14
);
//output dest however you want, e.g., std::copy

Answer 2

像这样的东西（A是传入的向量，N你想找到的最大的数，v成为结果向量）：

vector<T> v(N, 0);   
for each element in A:
   if (element > v[N-1])
       for(i = N-1; i > 0 && v[i] < element; i--)
          v[i] = v[i-1];
       v[i] = element;

这是某种“伪 C++”，不完全是 C++，但希望描述您将如何做到这一点。

Answer 3

复制和排序是一种选择吗？我的意思是，如果您的应用程序对性能不是那么严格，这是最简单（并且渐进地还不错）的方法！