众数问题

Time Limit: 2000 ms Memory Limit: 65536 KiB

Problem Description

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。如果出现多个众数，请输出最小的那个。

Input

输入数据的第1行是多重集S中元素个数n（n<1300000）；接下来的n行中，每行有一个最多含有5位数字的自然数，。

Output

输出数据的第1行给出众数，第2行是重数。

Sample Input

Sample Output

2
3

Hint

Source

分治解决

当然桶排序解决这个问题，更简单；

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int maxNum,maxCount;
 4 vector<int> vt,leftMax,rightMax,Max;
 5 vector<int> fun(vector<int>&v ,int left,int right){
 6     vt.clear();
 7     if(left==right){vt.push_back(v[left]);vt.push_back(1);return vt;}//存进去 数据 ，个数为1 
 8     if(left>right) return vt;//越界 返回
 9     int mid=(left+right)/2;
10     leftMax=fun(v,left,mid);//求得左边的最大 值  {数据,个数}
11     rightMax=fun(v,mid+1,right);//右边的 最大值  {数据,个数}
12     int midCount=0,midNum=0;//中间的 最大值，和个数 初始为0
13     if(v[mid]==v[mid+1]){//计算中间的 值 和个数
14             midNum=v[mid];
15             for(int i=mid;i>=left;i--){//从中间往左  进行 统计
16                 if(v[i]==v[mid])   midCount++;
17                 else break;
18             }
19             for(int i=mid+1;i<=right;i++){//从中间往右进行 统计
20                 if(v[i]==v[mid]) midCount++;
21                 else break;
22             }
23     }//这三个 数据 依次 对 已更新的 最大值数据 和个数  进行比较 ，继续更新
24     if(leftMax[1]>maxCount){  maxNum=leftMax[0];  maxCount=leftMax[1];  }
25     if(rightMax[1]>maxCount){ maxNum=rightMax[0]; maxCount=rightMax[1]; }
26     if(midCount>maxCount){    maxNum=midNum;      maxCount=midCount;    }
27     Max.clear();//将结果 存到vector里面 Max[0] 存的数据 Max[1]存的 个数
28     Max.push_back(maxNum);
29     Max.push_back(maxCount);
30     return Max;//返回结果
31 
32 }
33 
34 int main()
35 {
36     int n,data;
37     vector<int> v;
38     cin>>n;
39     for(int i=0;i<n;i++) {cin>>data;v.push_back(data);}
40     sort(v.begin(),v.end());//对结果 进行排序
41     maxNum=0,maxCount=0;
42     Max=fun(v,0,v.size()-1);
43     cout<<Max[0]<<endl;
44     cout<<Max[1]<<endl;
45     return 0;
46 }