[分治]查找最大和次大元素

题目简介

查找最大和次大元素

题目原思路

【问题求解】对于无序序列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=-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);	     //左区间求lmax1和lmax2
	int rmax1,rmax2;
	solve(a,mid+1,high,rmax1,rmax2);  //右区间求lmax1和lmax2
	if (lmax1>rmax1)
	{   max1=lmax1;
	    max2=max(lmax2,rmax1);	//lmax2,rmax1中求次大元素
	}
	else
	{   max1=rmax1;
	    max2=max(lmax1,rmax2);	//lmax1,rmax2中求次大元素
	}
    }
}

疑惑

1.lmax1,lmax2,rmax1,rmax2究竟什么时候被赋值了
2.为什么左递归到底的时候rmax1,rmax2会有值

更改

精简之后，方便查看代码逻辑
输出了过程中调用的所有变量

#include<climits>
#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 1e8;
int maxFis, maxSec;

int a[] = { 1,2,523,10,11,7,1,2,4,3 };
void solve(int a[], int l, int r, int &maxFis, int &maxSec)//&
{
	if (l == r){maxFis = a[l], maxSec = -INF;cout<<"size==1 "<<"l "<<l<<" r "<<r<<" maxFis "<<maxFis<<" maxSec "<<maxSec<<endl;cout<<endl;}
	else if (r-l==1){maxFis = max(a[l], a[r]), maxSec = min(a[l], a[r]);cout<<"size==2 "<<"l "<<l<<" r "<<r<<" maxFis "<<maxFis<<" maxSec "<<maxSec<<endl;cout<<endl;}
	else
	{
		int mid = l + r >> 1;
		int lmaxFis, lmaxSec,rmaxFis, rmaxSec;//回溯到底 回溯上来之后 才会走右边
		solve(a, l, mid, lmaxFis, lmaxSec),solve(a, mid + 1, r, rmaxFis, rmaxSec);//& max1 max2 直接传值到 lmax1 lmax2 rmax1 rmax2

        cout<<"size>2 "<<"l "<<l<<" mid "<<mid<<" r "<<r<<" lmaxFis "<<lmaxFis<<" lmaxSec "<<lmaxSec<<" rmaxFis "<<rmaxFis<<" rmaxSec "<<rmaxSec<<endl;
        cout<<endl;
		if (lmaxFis > rmaxFis)maxFis = lmaxFis,maxSec = max(lmaxSec, rmaxFis);	//lmax2,rmax1中求次大元素
		else maxFis = rmaxFis,maxSec = max(lmaxFis, rmaxSec);	//lmax1,rmax2中求次大元素
	}
}

int main()
{
    cout<<"数组元素";
    for(auto op:a)cout<<op<<" ";
    cout<<endl;
	solve(a, 0, sizeof a / 4, maxFis, maxSec);

    cout<<maxFis<<" "<<maxSec;

	return 0;
}

数据

数组元素1 2 523 10 11 7 1 2 4 3 
size==2 l 0 r 1 maxFis 2 maxSec 1

size==1 l 2 r 2 maxFis 523 maxSec -100000000

size>2 l 0 mid 1 r 2 lmaxFis 2 lmaxSec 1 rmaxFis 523 rmaxSec -100000000

size==2 l 3 r 4 maxFis 11 maxSec 10

size==1 l 5 r 5 maxFis 7 maxSec -100000000

size>2 l 3 mid 4 r 5 lmaxFis 11 lmaxSec 10 rmaxFis 7 rmaxSec -100000000

size>2 l 0 mid 2 r 5 lmaxFis 523 lmaxSec 2 rmaxFis 11 rmaxSec 10

size==2 l 6 r 7 maxFis 2 maxSec 1

size==1 l 8 r 8 maxFis 4 maxSec -100000000

size>2 l 6 mid 7 r 8 lmaxFis 2 lmaxSec 1 rmaxFis 4 rmaxSec -100000000

size==2 l 9 r 10 maxFis 3 maxSec 0

size>2 l 6 mid 8 r 10 lmaxFis 4 lmaxSec 2 rmaxFis 3 rmaxSec 0

size>2 l 0 mid 5 r 10 lmaxFis 523 lmaxSec 11 rmaxFis 4 rmaxSec 3

523 11

简写

#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 1e8;
int maxFis, maxSec;

int a[] = { 1,2,523,10,11,7,1,2,4,3 };
void solve(int a[], int l, int r, int &maxFis, int &maxSec)
{
	if (l == r)maxFis = a[l], maxSec = -INF;
	else if (r-l==1)maxFis = max(a[l], a[r]), maxSec = min(a[l], a[r]);
	else
	{
		int mid = l + r >> 1;
		int lmaxFis, lmaxSec,rmaxFis, rmaxSec;
		solve(a, l, mid, lmaxFis, lmaxSec),solve(a, mid + 1, r, rmaxFis, rmaxSec);

		if (lmaxFis > rmaxFis)maxFis = lmaxFis,maxSec = max(lmaxSec, rmaxFis);	
		else maxFis = rmaxFis,maxSec = max(lmaxFis, rmaxSec);
	}
}

int main()
{
	solve(a, 0, sizeof a/4, maxFis, maxSec);

    cout<<maxFis<<" "<<maxSec;

	return 0;
}

思路

&方便传回值
&同时传值给lmaxFis,lmaxSec,rmaxFis,rmaxSec
分治细化到元素数量为1，更新最大值，
分治细化到元素数量为2，更新最大最小值，
分治细化到元素数量 >2, 比较更新两块的最大最小值

精简写法

#include<iostream>

using namespace std;

int nums[]={2,5,1,4,6,3};
int a,b;

void get(int l,int r,int &a,int &b)
{
    if(l==r)
    {
        if(nums[l]>a)b=a,a=nums[l];
        else b=max(nums[l],b);
        return ;
    }
    int mid = l+r>>1;
    get(l,mid,a,b),get(mid+1,r,a,b);    
}

int main()
{
    get(0,sizeof nums/4,a,b);
    
    cout<<a<<" "<<b;
    
    return 0;
}

思路2

直接细化到元素数量只有1的时候就维护最大最小。