Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1408187
  • 博文数量: 143
  • 博客积分: 10005
  • 博客等级: 上将
  • 技术积分: 1535
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-23 17:25
个人简介

淡泊明志 宁静致远

文章分类

全部博文(143)

文章存档

2011年(2)

2009年(1)

2007年(22)

2006年(118)

我的朋友

分类: C/C++

2007-07-13 10:12:02

【我解C语言面试题系列】012 查找整数数组中第二大的数

查找整数数组中第二大的数

 

题目:写一个函数找出一个整数数组中,第二大的数。【Mirosoft

PS1” 66,66,66,66,66 ”,则没有第二大数。

2” 99,99,88,86,68,66 ”,则最大数是88

下面我先给出查找最大数字的程序:

int GetFirstMaxNumber(int buffer[])

{

    int i,max;

 

    max = buffer[0];

    for(i=1;i

    {

       if(buffer[i] > max)

           max = buffer[i];

    }

   

    return max;

}

这个算法非常经典,时间复杂度是:O(N)。对于查找一个数组中的最大数字,我们至少要做的就是把数组扫描一遍,能在只扫描数组一遍的情况下就能解决问题的则算法已经是一个不错的算法的了。

查找第二大的数的算法就是在查找最大数的算法的基础上实现的,下面给出查找第二大数的程序:

 

#define  ARRSIZE             10

#define  MINNUMBER          0xFFFFFFFF

#define  FIND_SUCESS         1

#define  FIND_FAIL          0

int GetSecondMaxNumber(int buffer[],int *secondMax)

{

    int i,max;

 

    max = buffer[0];

    *secondMax = MINNUMBER;

    for(i=1;i

    {

       if(buffer[i] > max)

       {

            *secondMax = max;

           max = buffer[i];

       }

       else if (buffer[i] > *secondMax  && buffer[i] < max)

            *secondMax = buffer[i];

    }

    if(*secondMax == MINNUMBER) //The numbers are all the same.

       return FIND_FAIL;

 

    return FIND_SUCESS;

}

查找第二大数实际上是伴随在查找最大数的过程中的。

1、如果当前元素大于最大数 max,则让第二大数等于原来的最大数 max,再把当前元素的值赋给 max。

2、 如果当前的元素大于第二大数secondMax的值而小于最大数max的值,则要把当前元素的值赋给 secondMax。――判断条件不能仅仅只是大于第二大的数secondMax,否则我们便无法处理” 99,99,88,86,68,66 ”这种情况。

PS:这个函数在调用时需要判断函数的返回值是否是 FIND_SUCESS 才能使用。


阅读(8069) | 评论(8) | 转发(1) |
给主人留下些什么吧!~~

chinaunix网友2010-05-04 15:46:17

ls的朋友,如果a[0]就是最大值的话,你的程序就有问题了。。。。

chinaunix网友2009-09-06 13:10:44

#include "stdio.h" main() { int a[10]={10,-3,12,32,91,11,23,14,117,42}; int i,max,second; max=a[0]; for(i=0;i<10;i++) { if(max

chinaunix网友2009-03-11 11:33:26

貌似可以把两个函数合并成为一个,这样可以使得时间还有代码都更简练一点,不过时间复杂度还是n。

chinaunix网友2008-11-23 13:03:45

好像还是有点bug,0xFFFFFFFF应该是-1,不是int类型的最小值,这使得某些序列还是无法判断。另外此程序如何能做到可移植性好呢?

chinaunix网友2008-10-10 04:02:08

还以为是n+logn-2次比较的算法。。