今天来说一个简单的需求:在一个序列中找到第二大的元素。
一眼看到这个问题,感觉解决的方法有很多,因为这并不是一个困难的问题。随便一想,能有下面几种解法:
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;
}
相信看过代码,大家更清楚了吧,是不是很简单,而且只用了一次循环。这个问题很简单,写这个的目的就是要提醒自己,遇到问题要先多想一想,而不是一味的使用简单暴力的方法,多想半个小时有时会省上一天甚至更多的时间。
当然这个方法不一定是最好的,希望大家多多拍砖。
后记:之前提交了一个有错误的版本,可以说是给自己一个教训,还没有进行测试就放了上去,以至于犯了一个很基本的错误。看来以后还是要多试一下,不能太盲目自信了。这个版本是经过测试的,应该是个可用版本。如果大家发现有什么数据会导致错误,欢迎再指出。
联系客服