分治法求数组最大元素与最小元素

2013年4月16日 由 Creater 留言 »

思想:

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

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

#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;
}
广告位

发表评论

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