題目1?落單的數
給出2*n + 1?個的數字，除其中一個數字之外其他每個數字均出現兩次，找到這個數字。
鏈接：http://www.lintcode.com/zh-cn/problem/single-number/
樣例
給出?[1,2,2,1,3,4,3]，返回 4
挑戰
一次遍歷，常數級的額外空間復雜度
解決方案
方法1思路：將所有的數轉換成二進制，因為是int類型，共32位。申請常數級（32位）的額外空間，然后每個數對應的位相加，最后對應位上的和模2。最后的結果就是單個數對應的二進制數。
class Solution { public:/*** @param A: Array of integers.* return: The single number.*/int singleNumber(vector<int> &A) {// write your code hereint ans[35];memset(ans, 0, sizeof(ans));for(int i=0; i<A.size(); ++i){for(int k=0; k<32; k++)ans[k] = (ans[k]+((A[i]>>k)&1))%2;}int ret = 0;int base = 1;for(int i=0; i<32; ++i){ret += ans[i]*base;base *= 2;}return ret;} };
方法2思路：通過異或，相同的數結果為0，那么最后的結果一定是落單的數字。
class Solution { public:/*** @param A: Array of integers.* return: The single number.*/int singleNumber(vector<int> &A) {// write your code hereint ans = 0;for(int i=0; i<A.size(); ++i)ans ^= A[i];return ans;} };
題目2?落單的數?II
給出3*n + 1 個的數字，除其中一個數字之外其他每個數字均出現三次，找到這個數字。
鏈接：http://www.lintcode.com/zh-cn/problem/single-number-ii/
樣例
給出?[1,1,2,3,3,3,2,2,4,1]?，返回 4
挑戰
一次遍歷，常數級的額外空間復雜度
解決方案
同上一題的方法1一樣的思路。
class Solution { public:/*** @param A : An integer array* @return : An integer */int singleNumberII(vector<int> &A) {// write your code hereint ans[35];memset(ans, 0, sizeof(ans));for(int i=0; i<A.size(); ++i){for(int k=0; k<32; k++)ans[k] = (ans[k]+((A[i]>>k)&1))%3;}int ret = 0;int base = 1;for(int i=0; i<32; ++i){ret += ans[i]*base;base *= 2;}return ret;} };
?
題目3：落單的數?III
給出2*n + 2個的數字，除其中兩個數字之外其他每個數字均出現兩次，找到這兩個數字。
鏈接：http://www.lintcode.com/zh-cn/problem/single-number-iii/
樣例
給出?[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。
class Solution { public:/*** @param A : An integer array* @return : Two integers*/int findNum(int k, vector<int> &A, bool flag){int ret = 0;for(int i=0; i<A.size(); ++i){if(flag && (1<<k)&A[i])ret ^= A[i];if(!flag && !((1<<k)&A[i]))ret ^= A[i];}return ret;}vector<int> singleNumberIII(vector<int> &A) {// write your code hereint x = 0;for(int i=0; i<A.size(); ++i)x ^= A[i];int k = 0;for(k; k<32; ++k)//找到異或值最后一個1，說明該位置P之后，兩個不同的數對應的二進制是相同的if((1<<k)&x)break;//根據這個位置P，轉換成“2*m+1個數字，除了一個數字其他數字均出現兩次”的問題//將位置P上對應為1的數字異或得到一個數字，然后再將位置P上對應為0的數字異或得到一個數字，最后得到答案vector<int> ans;ans.push_back(findNum(k, A, true));ans.push_back(findNum(k, A, false));return ans;} };
?
