算法 || 分治法【查找最大元素和次大元素)】 #01-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法 || 分治法【查找最大元素和次大元素)】 #01。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分治法求解【查找最大元素和次大元素】

【问题描述】

对于给定的含有n元素的无序序列，求这个序列中最大和次大的两个不同的元素。例如：（2, 5, 1, 4, 6, 3），最大元素为6，次大元素为5。
【在无序数组a[low…high]中找到第一大和第二大的数。两数不同。】

【算法分析】

采用折半的方式，采用分治法求解。

分解：

情况1，如果数组a[low…high]只有一个数据，那么最大的数max1为a[low]。
情况2，如果数组a[low…high]有两个数据，那么比较两个数的大小，max1=max(low,high)，max2=min(low,high)。
情况3，如果数组a[low…high]有3个及以上数据，那么采用自顶向下的二路归并思路，设置一个 mid=(low+high)/2 将数组a[low…high]一分为二，递归地对两个子序列a[low…mid]和a[mid+1…high]继续分解，结束条件为子序列长度为1。求出左区间最大元素和第二大元素 lmax1,lmax2和右区间最大元素和第二大元素 rmax1,rmax2。

合并

如果左区间最大元素大于右区间最大元素，那么max=lmax1，然后比较右区间最大元素和左区间第二大元素的大小。反之亦然。

【代码】

编译环境：VS2017
编程语言：C++文章来源地址https://www.toymoban.com/news/detail-405959.html

//ex1.查找最大和次大元素
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 25
#define INF 0x3f3f3f3f

void Solve(int a[], int low, int high, int &max1, int &max2)
{
	if (low == high)
	{
		max1 = a[low];
		max2 = -INF;
	}
	else if (low == high - 1)
	{
		max1 = max(a[low], a[high]);
		max2 = min(a[low], a[high]);
	}
	else
	{
		int mid = (low + high) / 2;
		int lmax1, lmax2;
		Solve(a, low, mid, lmax1, lmax2);
		int rmax1, rmax2;
		Solve(a, mid + 1, high, rmax1, rmax2);
		if (lmax1 > rmax1)
		{
			max1 = lmax1;
			max2 = max(lmax2, rmax1);
		}
		else
		{
			max1 = rmax1;
			max2 = max(lmax1, rmax2);
		}
	}
}

int main()
{
	int a[MAXN];
	int n;
	int max1 = 0, max2 = 0;
	cout << "请输入数组的长度:";
	cin >> n;
	cout << "请依次输入数据：";
	for (int i = 0; i <= n; i++)
		cin >> a[i];
	Solve(a, 0, n, max1, max2);
	cout << "第一大和第二大的数据分别为：" << max1 << " ," << max2 << endl;
	system("pause");
	return 0;
}