Single Number l && ll

Single Number l:

和find duplicate正好相反，但是仍然可以用排序或hash table解决。排序以后，对每个坐标i，查找A[i-1], A[i+1]中是否有等于A[i]的，没有则为要找的数。或者用hash table/set来记录扫描过的数字。如果A[i]不在hash table中，则插入，如果已经在，则在hash table中删除，最后table中剩下的就是要找的数。但排序法事件复杂度是O(nlogn)，而hash table尽管是O(n)事件复杂度，需要o(n)的extra memory。

这题的终极解法是利用位运算中的异或：x^x = 0, x^0 = x。并且异或有交换律：1^1^0 = 0 = 1^0^1。所以如果将全部数字进行异或运算，所有重复元素都会被消除，最后的结果便是那个唯一的数。

xor bitwise operation ^, both 0 or 1 then 0, else 1; same 0, otherwise 1;

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

        return res;
    }
};

Single Number ll

即利用位运算来消除重复3次的数。以一个数组[14 14 14 9]为例，将每个数字以二进制表达：

1110
1110
1110
1001
_____
4331    对每一位进行求和
1001    对每一位的和做%3运算，来消去所有重复3次的数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int N = sizeof(int) * 8; // 8 bits one byte
        vector<int> count(N, 0);
        int res = 0;

        for (int i = N - 1; i >=0; --i) {
            int mask = 1 << i;
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j) {
                // !!!!
                if (nums[j] & mask) {
                    sum++;
                }
            }
            // bug: % > +-  > Bitwise left shift and right shift
            //res = res << 1 + sum % 3;
            //res = (res << 1) + (sum % 3); // correct too.
            res = (res << 1) + sum % 3;
        }

        return res;
    }
};