在O(n)时间复杂度内查找前三名算法 - c++编程基础

查找前三个最大或者前三个最小的数，相当于查找冠亚季前三名的算法了，应该如何做呢？

当然可以用堆做，时间效率很高，下面是个简易的方法。

查找前三个最大数算法：

1) 初始化三个数为INT_MIN

2) 循环

a) 如果当前元素大于第一名，更新第一名，且第三名=第二名；第二名=第一名；

b) 如果当前元素大于第二名，而且不等于第一名，那么更新第二名，而第三名=第二名；

c) 如果当前元素大于第三名，而且不等于第二名，那么更新第三名。

程序：

#include  
#include  
  
using namespace std;  
  
struct TriInts  
{  
    int champion;  
    int secd;  
    int thir;  
};  
  
void findFirstThreePlace(TriInts &thr, vector &vArray)  
{  
    thr.champion = INT_MIN;  
    thr.secd = INT_MIN;  
    thr.thir = INT_MIN;  
    if(vArray.empty()) return;  
  
    for (int i = 0; i < vArray.size(); i++)  
    {  
        if (vArray[i] > thr.champion)  
        {  
            thr.thir = thr.secd;  
            thr.secd = thr.champion;  
            thr.champion = vArray[i];  
        }  
        else if (vArray[i] >




 thr.secd && vArray[i] != thr.champion)  
        {  
            thr.thir = thr.secd;  
            thr.secd = vArray[i];  
        }  
        else if (vArray[i] > thr.thir  && vArray[i] != thr.secd)  
        {  
            thr.thir = vArray[i];  
        }  
    }  
}  
  
int main()   
{  
    int a[] = {2,5,7,9,3,11,20,13,16,38,29,22,13,68,55};  
    int az = sizeof(a) / sizeof(a[0]);  
    vector vArr(a, a+az);  
    TriInts ti;  
  
    findFirstThreePlace(ti, vArr);  
  
    if(ti.champion == INT_MIN)  
        cout<<"There is not competition!\n";  
    else  
        cout<<"The champion is: "<