分治法查找最大和次大元素

问题描述：对于给定的含有n个元素的无序序列，求这个序列中最大和次大的两个不同元素。

问题求解：对于无序序列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}。

 

对应的完整代码如下：

#include <iostream>
#include <cstdlib>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;

//查找最大和次大元素
void solve(int a[],int low,int high,int &max1,int &max2) {
    if (low==high) {                     //区间中只有一个元素
        max1 = a[low];
        max2 = INT_MIN;              //表示无穷小
    }
    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;                          //左区间中求lmax1和lmax2
        solve(a, low, mid, lmax1, lmax2);

        int rmax1, rmax2;                          //右区间中求rmax1和rmax2
        solve(a, mid + 1,high, rmax1, rmax2);

        if (lmax1> rmax1) {
            max1 = lmax1;
            max2 = max(lmax2, rmax1);              //lmax2、rmax1中求次大元素
        }
        else {
            max1 = rmax1;
            max2 = max(lmax1, rmax2);                 //lmax1、rmax2中求次大元素
        }

    }

}


int main() {
    int n = 0;
    cout << "请输入一个数组的元素个数" << endl;
    cin >> n;
    int *a = new int[n];
    cout << "请依次输入数组元素：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int max1, max2;
    solve(a,0,n-1, max1, max2);
    cout << "最大值为：" << max1 << " " << "次大值为:" << max2 << endl;

    system("pause");
}

 

输出结果为：

请输入一个数组的元素个数
9
请依次输入数组元素：
1 5 9 6 8 7 4 2 3
最大值为：9 次大值为:8
请按任意键继续. . .