136.SingleNumber.md

136.Single Number

描述：在一个数组中，有一个落单数字只出现一次，其他数字都是两次。 找出这个落单的数字。

1. 比特位操作：异或

• If we take XOR of zero and some bit, it will return that bit a⊕0 = a If we take XOR of two same bits, it will return 0 a⊕a = 0
• a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b So we can XOR all bits together to find the unique number.

2. Complexity Analysis Time complexity : O(n) Space complexity : O(1)
3. 实现

   class Solution {
   public:
       int singleNumber(vector<int>& nums) {
           int res=0;
           for(auto n:nums)
               res ^= n;
           return res;
       }
   };