题目：

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;
}