c++ - 找出 vector 中最大的 3 个数

Question

我正在尝试创建一个函数来获取 vector 中的 3 个最大数字。例如:数字:1 6 2 5 3 7 4结果:5 6 7

我想我可以对它们进行 DESC 排序，在开始时获取 3 个数字，然后再对它们进行 ASC 排序，但这会浪费内存分配和执行时间。我知道有一个更简单的解决方案，但我无法弄清楚。另一个问题是，如果我只有两个数字怎么办...

顺便说一句:我使用 BorlandC++ 3.1 作为编译器(我知道，很老了，但这就是我将在考试中使用的......)

谢谢你们。

LE:如果有人想知道更多关于我正在努力完成的事情，你可以查看代码:

#include<fstream.h>
#include<conio.h>

int v[1000], n;
ifstream f("bac.in");

void citire();
void afisare_a();
int ultima_cifra(int nr);
void sortare(int asc);

void main() {
    clrscr();
    citire();
    sortare(2);
    afisare_a();
    getch();
}

void citire() {
    f>>n;
    for(int i = 0; i < n; i++)
        f>>v[i];
        f.close();
}                            

void afisare_a() {
    for(int i = 0;i < n; i++)
            if(ultima_cifra(v[i]) == 5)
            cout<<v[i]<<" ";
}

int ultima_cifra(int nr) {
    return nr - 10 * ( nr / 10 );
}

void sortare(int asc) {
    int aux, s;
        if(asc == 1)
        do {
            s = 0;
            for(int i = 0; i < n-1; i++)
                if(v[i] > v[i+1]) {
                    aux = v[i];
                    v[i] = v[i+1];
                    v[i+1] = aux;
                    s = 1;
                }
        } while( s == 1);
    else
        do {
            s = 0;
            for(int i = 0; i < n-1; i++)
                if(v[i] < v[i+1]) {
                    aux = v[i];
                    v[i] = v[i+1];
                    v[i+1] = v[i];
                                        s = 1;
                }
                } while(s == 1);
}

城市 = 阅读Afisare = 显示Ultima Cifra = 数字的最后一位Sortare = 冒泡排序

Answer 1

如果您使用的是现代编译器，您可以使用 std::nth_element 找到前三个。照原样，您必须在任何给定时间扫描数组，跟踪迄今为止看到的三个最大元素，当您到达最后时，这些将是您的答案。

对于管理起来微不足道的三个元素。如果您必须在 N 可能相当大时执行 N 个最大(或最小)元素，那么您几乎肯定会想要使用 Hoare 的 select 算法，就像 std::nth_element 确实如此。