• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2013-04-13)  算法/数据结构 |   抢沙发  37 
    文章评分 0 次,平均分 0.0

    题目:对于一个由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;
    }
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/572.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享