LeetCode 137. Single Number II [Medium] [C++] 解題筆記

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

 

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

想法:

    這題和 136. Single Number 一樣都要求用 O(n) time， O(1) space 解決，因此就不能簡單地用 hash map儲存

出現過的數字。這裡一樣要用 "Bitwise Operation" 來做，主要有兩種做法但概念類似，關鍵都在於說題目限制除了答案以外

的每個數字皆會出現剛好3次，因此我們可以用 shift 的操作來累加每一個位數，然後對 3 取餘數，只要single number 含有該位數

則該位數就不會是3的倍數就會被留下來。另一種方式是用三個變數 one, two, three 分別記錄出現一次,二次,三次的位數，

每次只要某個位數累計到3次就會被歸零(相當於第一種解法取餘數的概念)，因此最後在 one 中剩下的位數就是single number。

完整程式碼:

/* Bitwise manipulation 
 * O(n) time, O(1) space */
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        // int 有 32 bit，因為每個數字都會出現剛好三次，所以答案的數字的每一個位數會出現至少 1 次 or 大於 3 次
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                // 表示第 i 位數出現的次數
                sum += (nums[j] >> i) & 1;
            }
            // 只有答案的數字有的位數會被留下 (其他位數都會出現剛好三次)
            res |= (sum % 3) << i;
        }
        return res;
    }
};
/* Bit manipulation 
 * awesome
 * O(n) time, O(1) space */
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0;
        int two = 0;
        int three = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 已經出現一次 + 目前的 nums[i] 也是 1
            two |= one & nums[i];
            // 已經出現過一次 => 歸 0 (因為進位成 2 了), 未出現過 => 1
            one ^= nums[i];
            // 已經出現過兩次 + 目前的 nums[i] 也是 1 (存在 one 中)
            three = one & two;
            // 當出現 3 次時 將 one, two 歸 0 (因為每個數字一定出現 3次)
            one &= ~three;
            two &= ~three;
        }
        
        return one;
    }
};