当前位置:   article > 正文

分治法求解查找问题_对于给定的含有n个元素的无序序列,求这个序列中最小和次小的两个不同元素。 样例

对于给定的含有n个元素的无序序列,求这个序列中最小和次小的两个不同元素。 样例

查找最大和次大元素

问题描述

对于给定的含有n元素的无序序列,求这个序列中最大和次大的两个不同的元素。
例如:(2, 5, 1, 4, 6, 3),最大元素为6,次大元素为5。

问题求解

对于无序序列a[low.high]中,采用分治法求最大元素max1和次大元素max2的过程如下:
(1)a[low.high]中只有一个元素:则max1=a[low],max2=-INF(-∞)(要求它们是不同的元素)。
(2)a[low.high]中只有两个元素:则max1=MAX{a[low],a[high]},max2=MIN{a[low],a[high]}。
(3)a[low.high]中有两个以上元素:按中间位置mid=(low+high)/2划分为a[low…mid]和a[mid+1…high]左右两个区间(注意左区间包含a[mid]元素)。
求出左区间最大元素lmax1和次大元素lmax2,求出右区间最大元素rmax1和次大元素rmax2。
合并:若lmax1>rmax1,则max1=lmax1,max2=MAX{lmax2,rmax1};否则max1=rmax1,max2=MAX{lmax1,rmax2}。

代码

void solve(int a[], int low, int high, int &max1, int &max2)
{
	if (low == high)//区间仅一个元素
	{
		max1 = a[low];
		max2 = -INFINITY;
	}
	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(rmax2, lmax1);
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

算法分析

对于solve(a,0,n-1,max1,max2)调用,其比较次数的递推式为:
T(1)=T(2)=1
T(n)=2T(n/2)+1 //合并的时间为O(1)
可以推导出T(n)=O(n)。

折半查找

基本思路

设a[low…high]是当前的查找区间,首先确定该区间的中点位置mid=(low+high)/2;然后将待查的k值与a[mid].key比较:
(1)若k==a[mid],则查找成功并返回该元素的物理下标;
(2)若k<a[mid],则由表的有序性可知a[mid…high]均大于k,因此若表中存在关键字等于k的元素,则该元素必定位于左子表a[low…mid-1]中,故新的查找区间是左子表a[low…mid-1];
(3)若k>a[mid],则要查找的k必在位于右子表a[mid+1…high]中,即新的查找区间是右子表a[mid+1…high]。
下一次查找是针对新的查找区间进行的。

代码

int BinSearch(int a[], int low, int high, int k)
{
	int mid;
	if (low <= high)
	{
		int mid = (low + high) / 2;
		if (a[mid] == k)
			return mid;
		if (a[mid] > k)//中间位置的元素大于待查找元素
			return BinSearch(a, low, mid - 1, k);
		else//中间位置的元素小于待查找元素
			return BinSearch(a, mid + 1, high, k);
	}
	else
		return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

算法分析

折半查找算法的主要时间花费在元素比较上,对于含有n个元素的有序表,采用折半查找时最坏情况下的元素比较次数为C(n),则有:
在这里插入图片描述
由此得到:C(n)≤log2n+1
折半查找的主要时间花在元素比较上,所以算法的时间复杂度为O(log2n)。

寻找一个序列中第k小元素

问题描述

对于给定的含有n元素的无序序列,求这个序列中第k(1≤k≤n)小的元素。

问题求解

假设无序序列存放在a[0…n-1]中,若将a递增排序,则第k小的元素为a[k-1]。
采用类似于快速排序的思想。
对于序列a[s…t],在其中查找第k小元素的过程如下:
将a[s]作为基准划分,其对应下标为i。3种情况:
若k-1=i,a[i]即为所求,返回a[i]。
若k-1<i,第k小的元素应在a[s…i-1]子序列中,递归在该子序列中求解并返回其结果。
若k-1>i,第k小的元素应在a[i+1…t]子序列中,递归在该子序列中求解并返回其结果。

代码

int QuickSelect(int a[], int s, int t, int k)
{
	int i = s, j = t, tmp;
	if (s < t)
	{
		//快速排序
		tmp = a[s];
		while (i != j)
		{
			while (j > i&&a[j] >= tmp)
				j--;
			a[i] = a[j];
			while (i < j&&a[i] <= tmp)
				i++;
			a[j] = a[i];
		}
		a[i] = tmp;

		if (k - 1 == i)
			return a[i];
		else if (k - 1 < i)
			return QuickSelect(a, s, i - 1, k);
		else
			return QuickSelect(a, i + 1, t, k);
	}
	else if (s == t && s == k - 1)
		return a[k - 1];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

算法分析

对于QuickSelect(a,s,t,k)算法,设序列a中含有n个元素,其比较次数的递推式为:
T(n)=T(n/2)+O(n)
可以推导出T(n)=O(n),这是最好的情况,即每次划分的基准恰好是中位数,将一个序列划分为长度大致相等的两个子序列。
在最坏情况下,每次划分的基准恰好是序列中的最大值或最小值,则处理区间只比上一次减少1个元素,此时比较次数为O(n2)。
在平均情况下该算法的时间复杂度为O(n)。

寻找两个等长有序序列的中位数

问题描述

对于一个长度为n的有序序列(假设均为升序序列)a[0…n-1],处于中间位置的元素称为a的中位数。
设计一个算法求给定的两个有序序列的中位数。  
例如,若序列a=(11,13,15,17,19),其中位数是15,若b=(2,4,6,8,20),其中位数为6。两个等长有序序列的中位数是含它们所有元素的有序序列的中位数,例如a、b两个有序序列的中位数为11。

问题求解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

int midnum(int a[], int s1, int t1, int b[], int s2, int t2)
{
	int m1, m2;
	if (s1 == t1 && s2 == t2)//只含有一个元素
		return a[s1] < b[s2] ? a[s1] : b[s2];
	else
	{
		m1 = (s1 + t1) / 2;
		m2 = (s2 + t2) / 2;
		if (a[m1] == b[m2])//两序列中位数相等
			return a[m1];
		if (a[m1] < b[m2])
		{
			return midnum(a, m1, t1, b, s2, m2);//中位数小的取后半部分,中位数大的取前半部分
		}
		else
		{
			return midnum(a, s1, m1, b, m2, t2);//中位数大的取前半部分,中位数小的取后半部分
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

算法分析

对于含有n个元素的有序序列a和b,设调用midnum(a,0,n-1,b,0,n-1)求中位数的执行时间为T(n),显然有以下递归式:
T(n)=1 当n=1
T(n)=T(n/2)+1 当n>1
容易推出,T(n)=O(log2n)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/81986
推荐阅读
相关标签
  

闽ICP备14008679号