题目：在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数，并分析算法的时间复杂度。
答：问题分析：考虑序列中出现次数最多的数有多个，即出现多个众数，因此需要一个一维数组mode[]存储这些众数。使用分治法找出所有的众数，首先将输入元素从小到大进行排序，然后找到与a[mid]相等的数的范围a[mid_l..mid_r]。如果l~mid_l的长度大于等于mid_l~mid_r的长度，需要在l~mid_l范围内继续找，如果mid_r~r的长度大于等于mid_l~mid_r的长度，需要在mid_r~r中继续找。
算法设计：使用sort()对输入序列从小到大进行排序，找到与a[mid]相等的数的范围a[mid_l..mid_r]，然后进行判断（因为可能有多个众数，所以是大于等于）：
if(mid_l-l>=cnt_max){
findMode(l,mid_l-1,a);
}
if(r-mid_r>=cnt_max){
findMode(mid_r+1,r,a);
}
设当前找到的众数的出现次数为cnt_max，众数个数为mode_cnt。如果出现了新的最大值，则重新计数，新出现的最大值赋给cnt_max，mode_cnt为1；如果出现了和当前最大值一样的数，mode[mode_cnt++]=a[mid]。
int cnt=mid_r-mid_l+1;//a[mid]的出现次数
if(cnt>cnt_max){
cnt_max=cnt;
mode_cnt=0;//原来的众数清零
mode[mode_cnt++]=a[mid];//重新放入
}else if(cnt==cnt_max){
mode[mode_cnt++]=a[mid];
}
时间复杂度分析： sort()排序的时间复杂度为O(nlogn)，findMode()函数的时间复杂度递推公式为T(n)=2T(n/2)+O(n)。
T(n)=2T(n/2)+nO(1)=22T(n/22)+n+n=23T(n/23)+n+n+n=…=2kT(n/2k)+kn
令n=2k，T(n)=nT(1)+nlogn=n+nlogn。
时间复杂度也为O(nlogn)，所以该算法的平均时间复杂度为O(nlogn)。
具体代码：
#include<iostream>
#include<algorithm>
using namespace std;
int mode[10];//众数
int mode_cnt;//众数的个数
int cnt_max;//众数出现次数
void findMode(int l,int r,int a[]){//找众数（众数只有一个）
int mid=(l+r)>>1;
int mid_l,mid_r;//和a[mid]相等的数的范围a[mid_l..mid_r]
for(int i=l;i<=mid;i++){
if(a[i]==a[mid]){
mid_l=i;
break;
}
}
for(int i=mid;i<=r;i++){
if(a[i]==a[mid]){
mid_r=i;
}else{
break;
}
}
int cnt=mid_r-mid_l+1;//a[mid]的出现次数
if(cnt>cnt_max){
cnt_max=cnt;
mode_cnt=0;//原来的众数清零
mode[mode_cnt++]=a[mid];//重新放入
}else if(cnt==cnt_max){
mode[mode_cnt++]=a[mid];
}
if(mid_l-l>=cnt_max){
findMode(l,mid_l-1,a);
}
if(r-mid_r>=cnt_max){
findMode(mid_r+1,r,a);
}
}
int main(){
int n;
cout<<"请输入元素个数：";
cin>>n;
cout<<"请输入各个元素：";
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
findMode(0,n-1,a);
cout<<"众数为："<<endl;
for(int i=0;i<mode_cnt;i++){
cout<<mode[i]<<" ";
}
return 0;
}
思路2：不进行排序，通过快排将小于等于基准数的数全部放在左边，同时统计与基准数相等的数的个数，将大于基准数的数全部放在右边。一次快排结束后可以得到基准数的下标pos以及基准数出现的个数cnt，将cnt与cnt_max比较来判断该基准数是否为众数。分治：如果pos-l大于等于cnt_max（依然考虑有多个众数），则继续在左边找，右边同理。
具体代码：
ream>
#include<algorithm>
using namespace std;
int mode[10];//众数
int mode_cnt;//众数的个数
int cnt_max;//众数出现次数的最大值
void findMode(int l,int r,int a[]){
if(l>r) return;
int cnt=1;
int b=a[l];
//一次快排
int low=l,high=r;
while(low<high){
while(low<high&&a[high]>b) high--;
a[low]=a[high];
while(low<high&&a[low]<=b){
if(a[low]==b) cnt++;
low++;
}
a[high]=a[low];
}
a[low]=b;
int pos=low;
if(cnt>cnt_max){
cnt_max=cnt;
mode_cnt=0;//原来的众数清零
mode[mode_cnt++]=a[pos];//重新放入
}else if(cnt==cnt_max){
mode[mode_cnt++]=a[pos];
}
if(pos-l>=cnt_max){
findMode(l,pos-1,a);
}
if(r-pos>=cnt_max){
findMode(pos+1,r,a);
}
}
int main(){
int n;
cout<<"请输入元素个数：";
cin>>n;
cout<<"请输入各个元素：";
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
findMode(0,n-1,a);
cout<<"众数为："<<endl;
for(int i=0;i<mode_cnt;i++){
cout<<mode[i]<<" ";
}
return 0;
}
