寻找数组中第二大数

/*
 * 写一个函数找出一个整数数组中,第二大的数(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);
}

 

评论

2 楼 爱在爪哇 2012-05-21  

基偶双冒泡可以解决。

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不是非常小的情况。