0

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

谢谢!

4

3 回答 3

7

根据您对不修改原始向量的描述以及我认为您希望订单重要的假设,我建议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
于 2013-09-15T00:51:02.023 回答
0

像这样的东西(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++,但希望描述您将如何做到这一点。

于 2013-09-15T00:48:38.730 回答
0

复制和排序是一种选择吗?我的意思是,如果您的应用程序对性能不是那么严格,这是最简单(并且渐进地不错)的方法!

于 2013-09-15T00:41:48.940 回答