CF1003A Polycarp‘s Pockets 题解

题目传送门

方法一：桶排

一边输入，一边将第 $i$ 个数 $a_i$ 出现的次数存在一个数组 $b$ 的第 $a_i$ 个位置。输入完后遍历一次 $b$ 数组并取最大值就可以了。

时间复杂度：$O(n)$

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[105],b[105];
int ans;
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i],b[a[i]]++;for(int i=1;i<=n;i++)ans=max(ans,b[a[i]]);cout<<ans;return 0;
}

方法二：排序

这道题目 $a_i$ 的最大值仅有 $100$，所以桶排不会爆。但是如果 $a_i$ 的最大值达到 $10^8$，桶排就会爆了。因此我们可以用排序，将数组排序后计算连续相同的数的个数的最大值即可。

时间复杂度：$O(n\log n)$

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[105];
int ans,cnt=1;
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++){if(a[i]!=a[i-1])ans=max(ans,cnt),cnt=1;else cnt++;}ans=max(ans,cnt);cout<<ans;return 0;
}

完美撒花~