查找算法——找到序列中第二大的数

winston

今天来说一个简单的需求：在一个序列中找到第二大的元素。
一眼看到这个问题，感觉解决的方法有很多，因为这并不是一个困难的问题。随便一想，能有下面几种解法：
1 首先排序，然后取第二个位置的元素
2 循环遍历元素序列，找到最大的元素，然后将其移除。再重复此过程，得到第二大的元素
当然还有其他的思路，这里就不一一列举了。如果大家有什么好的想法，可以给我留言，咱们一起探讨。

仔细分析一下，不难发现，上面的方法虽然可以达到目的，但是效率都不高。第一种方法相当于一次排序过程，最快也要O(nlogn)的时间才能完成。而第二种方法更是需要循环遍历序列两次，O(n*n)的时间复杂度已经算是效率很低下了。试想一下，如果n相当大的情况下，n×n就会大的可怕了。这对于我们写软件的人来说，显然是不能容忍的。因此在这里，提出一个O(n)级别的方法，供大家借鉴参考。如果大家有好方法，欢迎提出。
废话不说，下面介绍算法思路：
我们既然可以循环遍历一次得到最大的元素，为什么不能保存住第二大的元素呢？当然可以，我们在比较元素大小时，只要把小的保存起来，经过一遍循环，这个元素就是第二大的元素了。
代码就更简单了

1. public static int find_second_biggest(int[] array){
2. int len = array.length;
3. int second = 0;
4. int max = array[0];
5. for (int i= 1; i<len ; i ++) {
6. if (max < array[i]){
7. second = max;
8. max = array[i];
9. }
10. }
11. return second;
12. }

复制代码

相信看过代码，大家更清楚了吧，是不是很简单，而且只用了一次循环。这个问题很简单，写这个的目的就是要提醒自己，遇到问题要先多想一想，而不是一味的使用简单暴力的方法，多想半个小时有时会省上一天甚至更多的时间。
当然这个方法不一定是最好的，希望大家多多拍砖。
本文链接

gissing20110808

楼主的思想非常好，不过代码 if (max < array[i]){ 这里缺少了点东西

if (max < array[i]){
second = max;
max = array[i];
}
else if(second < array[i])
{
second = array[i];
}


如果不加的话，像 100 90 80 98 89 这样第一个元素值的最大的序列求出来的不对

winston

gissing20110808 发表于 2012-3-8 16:07
楼主的思想非常好，不过代码 if (max < array){ 这里缺少了点东西

if (max < array){

文章转载，很难一一核对，多谢你指正。