找到向量中最大的3个数字

Question

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

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

BTW:我用作编译器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);
}

Citire =读取Afisare =显示Ultima Cifra =数字的最后一位数Sortare =冒泡排序

Answer 1

如果您使用的是现代编译器,则可以使用它std::nth_element来查找前三个.按原样,您必须扫描数组,跟踪到目前为止在任何给定时间看到的三个最大元素,当您到达结束时,这些将是您的答案.

对于要管理的三个要素来说,这是一个微不足道的事情.如果当N可能相当大时你必须做N个最大(或最小)的元素,那么你几乎肯定想要使用Hoare的select算法,就像std::nth_element那样.

Answer 2

你可以做到这一点而不需要排序,它可以在O(n)时间内使用线性搜索,3个变量保持你的3个最大数字(或者如果这个向量不会改变你的最大数字的索引).