# 137 - Single Number II

解法一 - Sort + 找出落單 element

這個解法滿直覺的，先把所有 element 都 sort 過，然後只要找落單的 element 就好，不過時間複雜度是 O(nlogn)。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int count = 1;
        for(int i = 1; i < nums.size(); ++i) {
            if(nums[i] != nums[i-1]) {
                if(count != 3) {
                    return nums[i-1];
                }
                else {
                    count = 1;
                }
            }
            else {
                ++count;
            }
        }

        return count != 3 ? nums[nums.size()-1] : -1 ;
    }
};

解法二 - Bit Manipulation

非常聰明的解法，實作如下：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int seenOnce = 0, seenTwice = 0;

        for(const int& num: nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }

        return seenOnce;
    }
};