算法1 :桶
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int f[N], a[N];
int n,m;
inline int read(int &x){
x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
int main(){
read(n);read(m);
for(int i = 1; i <= n; i++){
read(a[i]);
f[a[i]] ++ ;
}
for(int i = 1; i <= n; i ++){
if(f[a[i]] != 1) cout<<f[a[i]] - 1 <<endl;
else cout<<"BeiJu"<<endl;
}
return 0;
}
算法2: Hash
读者可以自行尝试,我比较懒
//模板: 开放寻址法
int f(int x){
return (x & size);
}
void get(int k){
int t = f(k);//按照一定的方法得到地址
while(v[t] != k &&v[t]){
t = t + 1 % size; //开的Hash大小
}
v[t] = k;
}
算法3: 并查集
//路径压缩
inline int find(int x){
return f[x] == x ? x : f[x] = find(f[x]);
}
//合并
void add(int x, int y){
f[find(x)] = f[find(y)];
}
//结果只要判断每一个树林的节点 == 1 ? BeiJu : size - 1;