Introduction

Given an array of integers, every element appears twice except for one. Find that single one.

最直观的想法就是遍历一遍把每个数出现的次数都存起来，然后再看谁的次数为1

1. Hash Table

If number has been in hash table, remove it from the dict. Return the only one number in the dict finally.

time O(n) space O(n),最后直接return字典的keys()

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m = {}
        for i in nums:
            if m.get(i):
                del m[i]
            else:
                m[i] = 1
        return m.keys()[0]

2. XOR

两个相同的数异或为0,0和任何数异或为任何数，例如：y ^ x ^ x = y; x ^ x = 0。所以对所有数字进行异或操作后剩下的就是那个只出现一次的数字。for loop要从list里第二个item开始。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = nums[0]
        for i in range(1, len(nums)):
            result ^= nums[i]
        return result