lintcode 落單的數（位操作）

　　給出2*n + 1 個的數字，除其中一個數字之外其他每個數字均出現兩次，找到這個數字。

　　給出 [1,2,2,1,3,4,3]，傳回 4

　　一次周遊，常數級的額外空間複雜度

　　方法1思路：将所有的數轉換成二進制，因為是int類型，共32位。申請常數級（32位）的額外空間，然後每個數對應的位相加，最後對應位上的和模2。最後的結果就是單個數對應的二進制數。

　　方法2思路：通過異或，相同的數結果為0，那麼最後的結果一定是落單的數字。

　　給出3*n + 1 個的數字，除其中一個數字之外其他每個數字均出現三次，找到這個數字。

　　給出 [1,1,2,3,3,3,2,2,4,1] ，傳回 4

　　同上一題的方法1一樣的思路。

　　給出2*n + 2個的數字，除其中兩個數字之外其他每個數字均出現兩次，找到這兩個數字。

　　給出 [1,2,2,3,4,4,5,3]，傳回 1和5

　　O(n)時間複雜度，O(1)的額外空間複雜度

　　　　　　

　　如上圖所示，所有數的異或的結果等于兩個落單數異或的結果（設為S）。如何根據這個異或的結果将落單的數找出來呢？首先，S的值一定不為0，那麼找到S對應的二進制數值為1的位（找到任意一個位為1都行， 這裡我們找到S的二進制最後一個為1的位，設為P），根據這一個位置，将所有的數劃分成兩部分，一部分是對應二進制P位是1，另一部分對應二進制P位是0。這樣就把兩個落單的數劃分到了不同的集合裡去了。如上圖的紅色框集合和綠色框集合。然後就轉換成“2*m+1個數字，除了一個數字其他數字均出現兩次”的問題，也就是題目1：落單的數I。