博文中会简要介绍Leetcode P0137题目分析及解题思路。

“Single Number II”这道题相对要难一点，是p0136的变形题，可以用HashTable来完成，也可以通过位运算的技巧。这里就不再阐述位运算的方法，我自己也不熟练就不班门弄斧了，这里我只附上使用HashTable的解法。

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?

以下是Java的题解代码实现。

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> num2CountMap = new HashMap<>();
        for (int num: nums)
            num2CountMap.put(num, num2CountMap.getOrDefault(num, 0)+1);
        
        for (Map.Entry<Integer, Integer> entry: num2CountMap.entrySet()) {
            if (entry.getValue() == 1)
                return entry.getKey();
        }
        
        return 0;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> num2count;
        for (int num: nums)
            ++num2count[num];
        
        for (auto &entry: num2count) {
            if (entry.second == 1)
                return entry.first;
        }
        
        return 0;
    }
};