🔗 🟡 260. Single Number III

tags: `雜湊表(Hash Table)` `位運算(Bit Manipulation)`

題意

給定一個整數陣列 $nums$ ，其中有 2 個元素恰好出現一次，其他元素都出現兩次。找出這 2 個只出現一次的元素。你可以以 任何順序 返回答案。

你必須設計並實現線性時間複雜度的算法，且只使用常數額外空間。

限制

$2 \leq nums.length \leq 3 \times 10^4$
$-2^{31} \leq nums[i] \leq 2^{31} - 1$

思路

方法一：雜湊表(Hash Table)

若忽略題目要求的後半部分，則可以使用雜湊表(Hash Table) 來計算每個元素出現的次數，最後從中找出只出現一次的元素即可。

複雜度分析

時間複雜度 $\mathcal{O}(n)$
空間複雜度 $\mathcal{O}(n)$

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # return [k for k, v in Counter(nums).items() if v == 1]
        cnt = Counter(nums)
        ans = []
        for k, v in cnt.items():
            if v == 1:
                ans.append(k)
        return ans

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        vector<int> ans;
        for (auto it = cnt.begin(); it != cnt.end(); it++) {
            if (it->second == 1) ans.push_back(it->first);
        }
        return ans;
    }
};

方法二：位運算(Bit Manipulation)

令出現一次的元素為 $a$ 和 $b$ ，則根據 XOR 的性質，將所有元素 XOR 起來，得到的結果 $s = a \oplus b$ 。由於 $a$ 和 $b$ 不相等，因此 $a \oplus b$ 必定不為 0，且至少有一位為 1。

由於 $a \oplus b$ 的某位為 1，因此可以根據該位是否為 1 將元素分成兩組，其中 $a$ 和 $b$ 分別在不同的組中，且除了 $a$ 和 $b$ 之外，其他元素都會出現兩次，如此便可以轉換成 136. Single Number 的問題，分別計算兩組元素的 XOR 和，即可得到 $a$ 和 $b$ 。

至於要取哪位作為分組的依據，可以取 $s$ 的最低位(low bit)的 1，即 $s \And -s$ ，這樣可以保證 $a$ 和 $b$ 在該位上不同。若對位運算不熟悉，可以參考參考資料。

由於題目限制中的 $-2^{31} \leq nums[i] \leq 2^{31} - 1$ ，若使用 int 來儲存 XOR 的結果，可能會有 overflow 的問題，因此可以使用 unsigned 來避免 overflow 。

複雜度分析

時間複雜度 $\mathcal{O}(n)$
空間複雜度 $\mathcal{O}(1)$

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for x in nums:
            xor ^= x
        lb = xor & -xor # 最低位的 1
        ans = [0, 0]
        for x in nums:
            ans[x & lb == 0] ^= x # 分組異或
        return ans

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned xor_sum = 0; // avoid overflow
        for (int x : nums) xor_sum ^= x;
        int lb = xor_sum & -xor_sum;
        vector<int> ans(2, 0);
        for (int x : nums) ans[(x & lb) == 0] ^= x;
        return ans;
    }
};