c++ - 在 vector 中找到 n 个最大值

Question

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

谢谢!

Answer 1

根据您关于不修改原始 vector 的描述以及我认为您希望顺序重要的假设，我建议 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