分治法求最大和次大元素

传统求一组数据内次最大和次大元素有顺序搜索法（时间复杂度O(n)），排序法（O(n*logn)）等。而分治法可以把时间复杂度降低到O(logn)级别，但是相对来说实现起来也复杂一点

code:

#include 
#include using namespace std;
const int INF = 0x3f3f3f3f;void solve(int a[], int left, int right, int &max1, int &max2)
{if(left == right)	// 递归出口，区间内只有一个元素 {max1 = a[left];max2 = -INF;}else if(left + 1 == right)	// 递归出口，区间内有两个元素 {max1 = max(a[left], a[right]);max2 = min(a[right], a[right]);}else{int mid = (left + right) / 2;int lmax1, lmax2;int rmax1, rmax2;solve(a, left, mid, lmax1, lmax2); 	// 递归寻找左边 solve(a, mid+1, right, rmax1, rmax2);	// 递归寻找右边 if(lmax1 > rmax1){max1 = lmax1;max2 = max(lmax2, rmax1);}else{max1 = rmax1;max2 = max(lmax1, rmax2);}}
}int main()
{int n;int a[1000];cin >> n;for(int i = 0; i < n; i++)cin >> a[i];int max1, max2;solve(a, 0, n-1, max1, max2);cout << max1 << " " << max2 << endl;return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！