题目：
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example1：
Input: [2,2,3,2]
Output: 3
Example2：
Input: [0,1,0,1,0,1,99]
Output: 99
思路1：
此题最简单粗暴的方法当然是使用HashMap了。记录下数组中每个数字出现的次数，最后返回出现次数为1的数字。
代码：
public int singleNumber(int[] nums) {
Map<Integer, Integer>map = new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
int num = map.get(nums[i]) + 1;
map.put(nums[i], num);
}else{
map.put(nums[i], 1);
}
}
int result = 0;
Iterator<Integer>ite = map.keySet().iterator();
while(ite.hasNext()){
int num = ite.next();
if(map.get(num) == 1){
result = num;
break;
}
}
return result;
}
思路2：
本题还有一问，要求在不使用任何额外空间的情况下跑出此题。若想这样解决问题唯有使用位运算了。此题有一点特殊性。除了出现次数为1的数字，其余数字出现的次数都为三次。因此这样的二进制表示的数字在同一位置上1出现的次数余三必为零。不为零的位置则是出现次数为一次的数字的位置。这个时候应该设定一个新的变量result，初始值设为零与该位进行相或操作。遍历完数组后返回这个result。
代码：
public int singleNumber2(int[] nums){
int result = 0;
for(int i=0;i<32;i++){
int bit = 1;
bit <<= i;
int count = 0;
for(int j=0;j<nums.length;j++){
if((bit&nums[j]) != 0){
count++;
}
}
if(count %3 != 0){
result |= bit;
}
}
return result;
}
