查找算法——找到序列中第二大的数(修正版)

 

今天来说一个简单的需求:在一个序列中找到第二大的元素。

一眼看到这个问题,感觉解决的方法有很多,因为这并不是一个困难的问题。随便一想,能有下面几种解法:

1 首先排序,然后取第二个位置的元素

2 循环遍历元素序列,找到最大的元素,然后将其移除。再重复此过程,得到第二大的元素

当然还有其他的思路,这里就不一一列举了。如果大家有什么好的想法,可以给我留言,咱们一起探讨。

仔细分析一下,不难发现,上面的方法虽然可以达到目的,但是效率都不高。第一种方法相当于一次排序过程,最快也要O(nlogn)的时间才能完成。 而第二种方法需要循环遍历序列两次,O(n)+O(n)的时间复杂度虽然不是无法接受,但毕竟还是要循环两次。对于我们写软件的人来说,显然希望代码是 “完美”的。因此在这里,提出一个只循环一次的方法,供大家借鉴参考。如果大家有好方法,欢迎提出。

废话不说,下面介绍算法思路:

我们既然可以循环遍历一次得到最大的元素,为什么不能保存住第二大的元素呢?当然可以,我们在比较元素大小时,只要把小的保存起来,经过一遍循环,这个元素就是第二大的元素了

代码就更简单了

复制代码
int find_second_biggest(vector<int> &v){
int len = v.size();
int max,second;
if (len < 2){
return -1;
}
if (v[0]>v[1]){
second = v[1];
max = v[0];
}
else{
second = v[0];
max = v[1];
}
for (int i=2; i< len; i++){
if(max < v[i]){
second = max;
max = v[i];
}
else if (second < v[i]){
second = v[i];
}
}
return second;
}
复制代码

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

原文地址:https://www.cnblogs.com/bb3q/p/4497458.html