HDU-2095 find your present (2)
代码(用STL的set)
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
scanf("%d", &n);
while(n!=0){
set<int> s;
int tmp;
for(int i=0; i<n; i++){
scanf("%d", &tmp);
if(s.find(tmp)==s.end()){
s.insert(tmp);
}
else{
s.erase(tmp);
}
}
printf("%d\n", *s.begin());
scanf("%d", &n);
}
return 0;
}
代码(用位异或运算)
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
while(n!=0){
int ans = 0;
for(int i=0; i<n; i++){
int tmp;
scanf("%d", &tmp);
ans = ans ^ tmp;
}
printf("%d\n", ans);
scanf("%d", &n);
}
return 0;
}
注解
1、方法一:用set,因为题目要求找出出现奇数次的数字,所以可在set中维持一个奇数次的集合,若当前出现数字在set中已存在,则加上本次变成偶数次,因此要从set中清理出来。否则,如果当前set中不存在该数字,表示当前为偶数次,再加上此次为奇数次,因此要insert进去。
2、方法二:位异或。位运算是使代码变简洁的很好的手段!a^a=0(a与自己异或,结果为0)。因此按位异或,最后的结果就是出现奇数次的那个数。