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

    思想:

    将数组划分成前后两部分,求前部分的最大值与最小值,再求后部分的最大值与最小值,则答案需要的最大值则是以上两部分的最大值,最小值为以上两部分的最小值。

    在前部分区间中,又可以划分前半部分和后半部分。由此可以递归解决,递归出口则为只有两个元素时直接比较大小,当然还得处理只有一个元素的数组。

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    void getMaxAndMin(int *a, int l, int r, int& minValue, int& maxValue)
    {
    	if(l == r) 
    	{
    		minValue = a[l];
    		maxValue = a[l];
    		return;
    	}
    	if(l + 1 == r)
    	{
    		maxValue = max(a[l], a[r]);
    		minValue = min(a[l], a[r]);
    		return;
    	}
    	int mid = l + (r - l) / 2;
    	int lMax, lMin, rMax, rMin;
    	getMaxAndMin(a, l, mid, lMin, lMax);
    	getMaxAndMin(a, mid + 1, r, rMin, rMax);
    	maxValue = max(lMax, rMax);
    	minValue = min(lMin, rMin);
    	return;
    }
    
    int main()
    {
    	int a[] = {1,8,2,4,89,22,33,-1,9};
    	int minValue, maxValue;
    	getMaxAndMin(a, 0, 8, minValue, maxValue);
    	cout<<minValue<<"  "<<maxValue<<endl;
    	return 0;
    }
     

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

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享