首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

找寻数组中第二大数

2012-12-24 
寻找数组中第二大数/* * 写一个函数找出一个整数数组中,第二大的数(microsoft) * 要求效率尽可能高 */#inc

寻找数组中第二大数

/* * 写一个函数找出一个整数数组中,第二大的数(microsoft) * 要求效率尽可能高 */#include<stdio.h>#include<stdlib.h>int find(int *a,int n){int i=1;int second=*(a+i);while(i<n){if(*(a+i)>second)second=*(a+i);i++;}return second;}int findsecondmaxvalue(int *a,int n){int i=0;int first=*(a+i);int second=*(a+i);while(i<n){if(*(a+i)>first){second=first;first=*(a+i);}else if(*(a+i)==first){//do nothing}else if(*(a+i)<first&&*(a+i)>second){second=*(a+i);}else{//do nothing}i++;}//最大值和次大值相等(只可能出现在数组的第一个元素)if(first==second){second=find(a,n);}return second;}int main(){int a[]={9,5,1,7,4,6,2,3,8};int n=sizeof(a)/sizeof(a[0]);int second=findsecondmaxvalue(a,n);printf("次大值=%d\n",second);}

?

1 楼 hubeen 2011-02-25   思路一:
最大值=array[0],次大值=array[1],遍历一次,每次比较并更新次大和最大值。最后可以第二大值,适用于前N大问题,N非常小的情况。
思路二:
middle=array[0],把所有小于middle的移动到middle左边。如果middle的index=1,第二大值=middle。否则在0到middle.index-1之间递归第一个过程。适合前N大问题,N不是非常小的情况。
思路三:
把array构造为最小堆,取第二次为第二大值。适合前N大问题,N不是非常小的情况。
2 楼 爱在爪哇 2012-05-21   基偶双冒泡可以解决。

热点排行