参考：
https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode/

list思路

1. 遍历 nums 中的每一个元素
2. 如果某个nums 中的数字是新出现的，则将它添加到列表中
3. 如果某个数字已经在列表中，删除它

时间复杂度O(n^2)，因为遍历列表有个n的复杂度，空间复杂度O(n)

哈希表

我们用哈希表避免每次查找元素是否存在需要的 O(n) 时间。

1. 遍历 sum 中的每一个元素
2. 查找是否有当前元素的键，如果没有，将当前元素作为键插入
3. 最后，哈希表中仅有一个元素，用 popitem 获得它

位操作

太骚了

class Solution:

    def singleNumber(self, nums) -> int:
        d = {}
        for i in nums:
            if d.get(i) is not None:
                d.pop(i)
            else:
                d[i] = 1
        return d.popitem()[0]
    def singleNumber3(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a


if __name__ == '__main__':
    s = Solution()
    a = s.singleNumber([1,2,2,3,3])
    print(a)

java代码

package T136只出现一次的数字;

import java.util.HashMap;

public class Solution {

    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>(nums.length / 2);
        for (int i : nums) {
            if (map.containsKey(i)) {
                map.remove(i);
            } else {
                map.put(i, 1);
            }
        }
        return map.entrySet().iterator().next().getKey();
    }

    public int singleNumber2(int[] nums) {
        int ans = 0;
        for (int num: nums) {
            ans = ans ^ num;
        }
        return ans;
    }
    public static void main(String args[]) {
        Solution s = new Solution();
        int a[] = {1, 2, 2, 3, 3};
        s.singleNumber(a);
    }
}