对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来?

2013年4月13日 由 Creater 留言 »

题目:对于一个由N个整数组成的数组,需要比较多少次才能把最大和最小的数找出来?

思路1:扫描一遍数组,找出最大的值以及最小的值。

分析:比较次数为2N

思路2:将数组中相邻的两个数分在同一组(这只是概念上的分组,无须任何实际的操作),然后可以利用两个变量Max和Min来存储当前的最大值和最小值,同一组的两个数进行比较,然后将较小的与Min比较更新,将较大的与Max比较更新,如此反复比较,直到遍历完整个数组。

分析:比较次数为1.5*N

思路3:使用分治思想,在N个数中求最小值Min和最大值Max,我们只需要分别求出前后N/2个数的Min和Max,然后取较小的Min,较大的Max即可。

分析:比较次数为1.5*N

扩展题目:如果需要找出该数组中的第二大数,需要比较多少次呢?

思路:一趟遍历即可,比较次数为在N到2N之间

int GetSecondMax(int arr[], int size)
{
	assert(arr!=NULL && size>=1);

	int maxNum = arr[0];
	int secondMax = arr[0];

	for (int i=1; i<size; i++)
	{
		if (maxNum < arr[i]) 		{ 			secondMax = maxNum; 			maxNum = arr[i]; 		} 		else if (arr[i] > secondMax)
			secondMax = arr[i];
	}
	return secondMax;
}
广告位

发表评论

你必须 登陆 方可发表评论.