在O(n)时间复杂度内查找前三名算法

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

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

查找前三个最大数算法：

1) 初始化三个数为INT_MIN

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

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

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

程序：

#include<iostream>
#include<vector>

using namespace std;

struct TriInts
{
	int champion;
	int secd;
	int thir;
};

void findFirstThreePlace(TriInts &thr, vector<int> &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<int> 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: "<<ti.champion<<endl;

	if(ti.secd == INT_MIN) 
		cout<<"There not second place!\n";
	else 
		cout<<"The second place is: "<<ti.secd<<endl;

	if(ti.thir == INT_MIN) 
		cout<<"There not third place!\n";
	else 
		cout<<"The third place is: "<<ti.thir<<endl;

	system("pause");
	return 0;
}

运行结果：