找回密码
 用户注册

QQ登录

只需一步,快速开始

查看: 7211|回复: 2

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

[复制链接]
发表于 2012-3-7 00:15:17 | 显示全部楼层 |阅读模式
今天来说一个简单的需求:在一个序列中找到第二大的元素。
一眼看到这个问题,感觉解决的方法有很多,因为这并不是一个困难的问题。随便一想,能有下面几种解法:
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. }
复制代码

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

发表于 2012-3-8 16:07:21 | 显示全部楼层
楼主的思想非常好,不过代码 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 这样第一个元素值的最大的序列求出来的不对
 楼主| 发表于 2012-3-8 16:53:44 | 显示全部楼层
gissing20110808 发表于 2012-3-8 16:07
楼主的思想非常好,不过代码 if (max < array){ 这里缺少了点东西

if (max < array){

文章转载,很难一一核对,多谢你指正。
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

Archiver|手机版|小黑屋|ACE Developer ( 京ICP备06055248号 )

GMT+8, 2024-3-29 02:52 , Processed in 0.021026 second(s), 7 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表