北邮oj-single number
简单说就是,输入n个数,除了其中一个数外,其余的数均出现3次,将单独的这一个数找出来。输入的数字可能会很大,int已经超出范围,要用long long
本题开始想到计数数组,但数值太大放弃,后来采用结构体
struct Data{
long long num;
int cnt;
}
边输入,边搜索是否已经出现,但时间复杂度较大,发生超时。
最后采用了map映射,将long long 映射为int,即可采用计数数组。
有点疑问的地方:map技术数组初值为0吗?
#include<bits/stdc++.h>
using namespace std;
//map映射建立long long的计数数组
int main(){
int n;
while(scanf("%d",&n)!=EOF){
map<long long,int> mp;
while(n--){
long long a;
scanf("%lld",&a);
mp[a]++;
}
for(map<long long,int>::iterator it=mp.begin();it!=mp.end();it++){
if(it->second==1){
printf("%lld\n",it->first);//一开始总体是答案错误,最后发现这里写成%d了,一定要细心
break;
}
}
}
return 0;
}