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行是重数。
Samples
Sample #1
| Input |
Output |
6
1
2
2
2
3
5 |
2
3 |
方法一:map映射法
算法分析
遍历多重集合$S$,由于本题考查的是集合的众数和重数，两者有一种天然的一一对应关系，可以使用一个map维护一个元素与其重数的映射关系。每遍历一个元素num，使map[num]++
遍历完成后，map中保存了每个元素的重数，然后遍历map，找到最大的重数，它就是要输出的重数，其对应的key就是要输出的众数。
std::map基于红黑树，其遍历顺序依据标准库要求按照键值升序遍历，符合题目要求:
如果出现多个众数，请输出最小的那个。
这也是为什么没有使用std::unordered_map的原因，因为它的遍历是无序的，基于哈希表实现，即使它的插入和查找操作达到了 $O(1)$
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| input(n)
for(i=0->n-1){
input(num)
map[num]++
}
int zs=0,cs=0
for(key in map){
if(map[key]>cs){
zs=key
cs=map[key]
}
}
print(zs)
print(cs)
|
具体实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
map<int,int> myMap;
int main(){
int n,num;
cin>>n;
for(int i=0;i<n;i++){
cin>>num;
myMap[num]++;
}
int zs=0,cs=0;
for(auto it=myMap.begin();it!=myMap.end();it++){
if(it->second>cs){
zs=it->first;
cs=it->second;
}
}
cout<<zs<<endl;
cout<<cs<<endl;
system("pause");
}
|
复杂度分析
$N1=0+\sum{i=1}^{n-1} log\ i=log \ (n-1)! $
第二个循环:
$N_2=n \cdot log \ n $
$N=N_1+N2=nlogn+log(n-1)!$
因为当$n>=1$时,$N_2>=N_1$
$proof:$
$令f(n)=log \ (n-1)!$
$g(n)=nlogn$
$做e的指数,不会改变两者的大小关系:$
$e^{f(n)}$和$e^{g(n)}$
$即:$
$e^{log \ (n-1)!}=(n-1)!$
$e^{nlogn}=n^n$
当$n>=1$时，$(n-1)!<=n^n$
即:$g(n)>=f(n),\ \ \ n>=1$
所以时间复杂度是$O(NlogN)$
方法二: 排序法
算法分析
可以通过排序来获得元素与其重数的对应关系，因为集合中的元素在排序后，相同的元素，肯定是排列在一起的。然后我们遍历排序后的S数组，使用打擂台的方式得出众数和重数。
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| input(n)
for(i=0->n-1){
input(s[i])
}
sort(s[])
int temp_zs=s[0],temp_cs=0,zs=0,cs=0;
for(i=0->n-1){
if(s[i]==temp_zs){
temp_cs++;
if(i!=s.size()-1)
continue;
}
else{
if(temp_cs>cs){
zs=temp_zs
cs=temp_cs;
}
temp_zs=s[i]
temp_cs=1
}
}
print(zs)
print(cs)
|
具体实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
vector<int> s;
void swap(vector<int>& a, int i, int j){
int temp=a[i];a[i]=a[j];a[j]=temp;
}
void qsort(int l,int r){
if(l>=r) return;
int i=l-1,j=r+1,mid=s[l+r>>1];
while(i<j){
do i++; while(s[i]<mid);
do j--; while(s[j]>mid);
if(i<j){
swap(s,i,j);
}
}
qsort(l,j);
qsort(j+1,r);
}
int main(){
int n,num;
cin>>n;
for(int i=0;i<n;i++){
cin>>num;
s.push_back(num);
}
qsort(0,n-1);
int temp_zs=s[0],temp_cs=0,zs=0,cs=0;
for(int i=0;i<s.size();i++){
if(s[i]==temp_zs){
temp_cs++;
if(i!=s.size()-1)
continue;
}
if(temp_cs>cs){
zs=temp_zs;
cs=temp_cs;
}
temp_zs=s[i];
temp_cs=1;
}
cout<<zs<<endl;
cout<<cs<<endl;
system("pause");
}
|
复杂度分析
第一个循环
$N_1=O(N)$
排序
$N_2=O(NlogN)$
第二个循环
$N_3=O(N)$
综上复杂度是$O(NlogN)$
方法三:分治法
算法分析
可以采用分治的思想，对于集合$S$中序列的众数和对应重数，我们可以将从$S$的规模入手，进行子问题的分割，递归的分割，直到集合分为单元素集合时，停止分割，此时每个单元素是该单元素集合的众数，重数是1,然后合并子问题，得到原集合$S$的众数和重数。此方法的难点之一是如何进行子问题的合并，我们可以采用关联容器map来保存元素和其重数的映射关系，这样保证了分割子问题之间的数据共享。
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| pair<int,int> findModeAndCount(int s[], int l, int r, myMap){
if(l==r){
mYmap[s[l]]++
return {s[l],myMap[s[l]]}
}
int mid = (l+r)>>1
pair<int,int> lRes=findModeAndCount(s,l,mid)
pair<int,int> rRes=findModeAndCount(s,mid+1,r)
if(lRes.second==rRes.second){
return lRes.first<rRes.first?lRes:rRes
}
else{
return lRes.second>rRes.second?lRes:rRes
}
}
main(){
input(n)
input(s[])
pair<int,int> res = findModeAndCount(0,n-1)
print(res.first)
print(res.second)
}
|
具体实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
pair<int,int> findModeAndCount(vector<int>& s, int l, int r, unordered_map<int, int>& myMap){
if(l==r){
myMap[s[l]]++;
return {s[l],myMap[s[l]]};
}
int mid = (l+r)>>1;
pair<int,int> lRes = findModeAndCount(s,l,mid,myMap);
pair<int,int> rRes = findModeAndCount(s,mid+1,r,myMap);
if(lRes.second==rRes.second){
return lRes.first<rRes.first?lRes:rRes;
}
else{
return lRes.second>rRes.second?lRes:rRes;
}
}
int main(){
vector<int> s;
unordered_map<int,int> myMap;
int n,num;
cin>>n;
for(int i=0;i<n;i++){
cin>>num;
s.push_back(num);
}
pair<int,int> res = findModeAndCount(s,0,n-1,myMap);
cout<<res.first<<endl;
cout<<res.second<<endl;
system("pause");
}
|
复杂度分析
输入$S$：
$O(N)$
函数findModeAndCount()
考虑分治策略，每次都是从集合的中部分割,每次递归内操作皆是常数操作，可以写出时间复杂函数的递推式:
依据解决关于递归函数时间复杂度的Master Theorem,$T(n)=aT(n/b)+f(n)$
$a=2,b=2,f(n)=O(1)$
$n^{log_b{a}}=n^{log_21}=1=f(n)$
$T(n)=O(n^{log_b{a}}logn)=O(logn)$
所以时间复杂度:$O(logN)$
综上时间复杂度是$O(N)$