统计重复个数,很容易想到hash,建立一个int数组,把电话号码的数字形式作为hashcode,数组记录出现的次数。
当有海量数据计算重复次数的时候,我们经常这么做,因为数据量相对于hashcode的范围来说是很大的,所以利用hash数组保存出现次数是划算的。
但是这道题hashcode的范围是0~1000000,而n与hashcode相当或更小,这时候hash数组平均下来就会有很多空间被浪费了。
不如反过来,利用一个int[n]的数组,保存的是hashcode,这样空间是全部充分利用的。如果要计算出现次数,那么最后把数组sort一下,相同hashcode的必然在一起,遍历一遍数组就可以知道哪些hashcode出现了多少次了。合计一下,多了个sort,少了很多空间。
以下是discuss里Pcz 童鞋的代码
#include <cstdio> #include <algorithm> using namespace std; char s[31]; int Hash() { int sum=0; for(int i=0,k=0;k<7;i++) { if(s[i]>='0'&&s[i]<='9') { sum*=10;k++; sum+=(s[i]-'0'); } else if(s[i]>='A'&&s[i]<'Z') { sum*=10;k++; sum+=((s[i]-'A'-(s[i]>'Q'))/3+2); } } return sum; } int main() { int n;scanf("%d",&n); int data[n];getchar(); for(int tmp=0;tmp<n;tmp++) { gets(s); data[tmp]=Hash(); } sort(data,data+n); bool p=false;n--; for(int i=0,num=1;i<n;i+=num=1) { while(data[i]==data[i+1]) { num++; i++; } if(num>1) { printf("%03d-%04d %d\n",data[i]/10000,data[i]%10000,num); p=true; } } if(!p)printf("No duplicates.\n"); return 0; }