分治算法解决众数求解
一般来讲分治算法需要处理的序列是有序的，所以该算法处理众数问题的时候也需要进行排序
分治算法适合于解决可以将问题规模减小的问题，直到这个小问题可以直接解决
这里还是需要想一下这个过程，如何用分治算法进行求解
不可能将所有子问题分解为单个数值的求解，但是我们可以做到的是将某一个出现很多次的数字进行统计
这也就是本体解决思路了，下面举一个例子（已经排序好的）：
| 1 | 2 | 2 | 3 | 3 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
经过排序以后，打算进行中间位置的数的求解，也就是先数3的个数（记录左右边界3,5）
然后在左边界的左边进行递归求解，在右边界的右边进行递归求解
在这个过程中有一个优化，如果左侧的数已经不足以大于当前的最大重数，那就没必要在进行统计左侧内容，右侧同理。
下面是代码
#includeusing namespace std;//找到从左，从右开始的跟a[mid]一样的数//得到左右边界为low,highvoid solve(int s[], int n, int& l, int& r){ int mid = n/2; for(l = 0 ; l < n ; l++){ if(s[l] == s[mid]) break; } for(r = l+1; r < n ; r++){ if(s[r] != s[mid]){ break; } }}void _MaxCnt(int &mid, int &maxCnt, int a[],int n){ int l, r; solve(a,n,l,r); int num = n/2; int cnt = r-l; //如果众数为当前，那就更新 if(cnt > maxCnt){ maxCnt = cnt; mid = a[num]; } //左侧进行递归查询 if(l+1 > maxCnt){ _MaxCnt(mid,maxCnt,a,l+1); } //右侧进行递归查询 if(n-r > maxCnt){ _MaxCnt(mid,maxCnt,a+r,n-r); }}int main(){ int a[] = {1,2,3,3,3,4,9,6,7,7,7,7,9,5,10,10,12, 12,14,14,15,14,31,23,5,23,4,43,3,2,3,4 ,3,2,1,1,34,2,3,2,2,2,22,0,2,12,5,5,5, 5,5,5,5,6,5}; int n = sizeof(a)/sizeof(a[0]); sort(a,a+n); int maxCnt = 0; int num = 0; _MaxCnt(num,maxCnt,a,n); cout << num << " " << maxCnt << endl; return 0;}