Given an 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?

思路

我们如果用最直白的方法，统计一下整型数组里面数字出现的次数即可。顺便熟悉了一下Java里面HashMap的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> stats = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++){
            if (stats.containsKey(nums[i])){
                int tmp = stats.get(nums[i]) + 1;
                stats.put(nums[i], tmp);
            }
            else{
                stats.put(nums[i], 1);
            }
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> e : stats.entrySet()){
            if (e.getValue() == 1) res = e.getKey();
        }
        return res;
    }
}

参考资料：

利用HashMap是无法达到线性空间复杂度的，我们可以参考这种方法。

https://discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions

这个……就很厉害了，用状态机的方法来做这道题。我们要想办法构建三个状态，等第三个状态进行完之后，状态机的状态回归0。实际上巧妙是利用位运算的方法来解决这个问题。