> For the complete documentation index, see [llms.txt](https://rachel2011.gitbook.io/leetcode_cc150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rachel2011.gitbook.io/leetcode_cc150/master.md).

# 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
```