众数问题 给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1,2,2,2,3,5}。多重集S的众数是2，其重数为3。 对于给定的由n个自然数组成的多重集S，计算S的众数及其重数。
方法一： 1输入数据存入数组 2数组排序 3记录每个数出现次数 4求出最大 输出
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int main() { int n,i,m=0,s,max=0,t,*a; //m标记元素，s统计该元素重数，max标记出现的最大，t表示该重数对应的元素 scanf("%d",&n);//输入个数 a=new int[n];//新建数组 for(i=0;i<n;i++){ scanf("%d",&a[i]); }//输入元素 存入数组 sort(a,a+n);//排序 for(i=0;i<n;i++) { if(m!=a[i]) s=1; else s++; m=a[i];//记录a[i]个数 if(s>max) { t=m; max=s;//找出最大的 } } printf("%d\n%d\n",t,max); return 0; }方法二： 分治递归 1排序求出中间值和中间值个数（在数组中的开始结尾的位置） 2中间值个数和左边比，左边少就不比，多就接着找中间值，再比 3右边同理
#include<iostream> #include<cstring> #include<stdio.h> #include<algorithm> using namespace std; void split(int a[],int n,int &l,int &r){ //将数组进行切割成两端 int mid = n/2; for(l = 0; l<n; ++l){ if(a[l] == a[mid]) break; } for(r = l+1;r<n;++r){ if(a[r] != a[mid]) break; } } //t表示众数 max表示重数 void getMax(int &mid,int &m, int a[],int n){ int l ,r; split(a,n,l,r); int t = n/2; int cnt = r - l; if(cnt > m){ m = cnt; mid = a[t]; } //l表示左边的个数，左边的个数必须大于中位数的个数，才有进行搜索的意义 if(l+1 > m){ getMax(mid, m, a, l+1); } //同理，右边的个数将要大于中位数的个数才有继续搜寻的意义，同时右边数组的起始位置进行改变 if(n-r > m){ getMax(mid, m, a+r, n-r); } } int main() { int n,*a; scanf("%d",&n);//输入个数 a=new int[n];//新建数组 for(int i=0;i<n;i++){ scanf("%d",&a[i]); }//输入元素 存入数组 sort(a,a+n);//排序 int m = 0; int t = 0; getMax(t ,m, a, n); printf("%d %d\n",t,m); return 0; }