分治法实现众数问题--例如（S={1|分治法实现众数问题--例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。） 2|2|3|5}，则多重集S的众数是2，

题目的描述：
例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。
【分治法实现众数问题--例如（S={1|分治法实现众数问题--例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。）】对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。
众数------一组元素中出现的次数是最多的
重数-------这个数出现的总次数

算法的分析：
1.采用分治法：
（1）先找到这一组的中位数，然后找到该数的左界限和右界限
（2）上面那一步是分割的第一组，找出了众数和重数
（3）在分治左边和右边
（4）每次分割后进行比较，把该众数最大值和该数的重数保留下来，递归结束

#include #include #include using namespace std; template void Split(Type *a,int &left,int &right,int n)///这里是函数的分割，极其关键 { int mid=n/2; ///中位数 for(left=0; left void Mode(Type *a,int &number,int &MaxTime,int n)///计算众数和重数 { int left,right; Split(a,left,right,n); ///先分割 int num=n/2; ///第一组的中位数（假设为众数） int cnt=right-left; ///第一组中位数的个数（重数） if(cnt>MaxTime)///进行作比较，每次把最大值进行保留下来 { MaxTime=cnt; number=a[num]; }if(left+1>MaxTime)///当左边的个数小于中位数的个数时，没有在比较下去的意义 { Mode(a,number,MaxTime,left+1); }if(n-right>MaxTime)///当右边的个数小于中位数的个数时，没有在比较下去的意义 { Mode(a,number,MaxTime,n-right); } }int main() { int a[] = {1,2,2,2,2,3,5,2,3,5,5,2,2,5,5,2,5,5}; int n = sizeof(a)/sizeof(a[0]); sort(a,a+n); int MaxTime = 0; int number = 0; Mode(a,number,MaxTime,n); printf("%d %d\n",number,MaxTime); return 0; }

运行结果如下：