# Single Number 「找單數」系列題，技巧性較強，需要靈活運用位運算的特性。 ### Source - lintcode: [(82) Single Number](http://www.lintcode.com/en/problem/single-number/) ~~~ Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return 4 Challenge One-pass, constant extra space ~~~ ### 題解 根據題意，共有`2*n + 1`個數，且有且僅有一個數落單，要找出相應的「單數」。鑒于有空間復雜度的要求，不可能使用另外一個數組來保存每個數出現的次數，考慮到異或運算的特性，根據`x ^ x = 0`和`x ^ 0 = x`可將給定數組的所有數依次異或，最后保留的即為結果。 ### C++ ~~~ class Solution { public: /** * @param A: Array of integers. * return: The single number. */ int singleNumber(vector<int> &A) { if (A.empty()) { return -1; } int result = 0; for (vector<int>::iterator iter = A.begin(); iter != A.end(); ++iter) { result = result ^ *iter; } return result; } }; ~~~ ### 源碼分析 1. 異常處理(OJ上對于空vector的期望結果為0，但個人認為-1更為合理) 1. 初始化返回結果`result`為0，因為`x ^ 0 = x`