題目資訊

• 題目編號: 2206
• 題目連結: Divide Array Into Equal Pairs
• 主題: Array, Hash Table, Bit Manipulation, Counting

題目敘述

您有一個整數數組 nums，由 $2 \times n$ 個整數組成。

您需要將 nums 分成 $n$ 對，使得：

• 每個元素恰好屬於一對。
• 一對中的元素是相等的。

如果可以將 nums 分成 $n$ 對，則返回 true，否則返回 false。

範例 1：

輸入：nums = [3,2,3,2,2,2]
輸出：true
解釋： 
nums 中有 6 個元素，所以應該分成 6 / 2 = 3 對。
如果 nums 被分成對 (2, 2), (3, 3), 和 (2, 2)，它將滿足所有條件。

範例 2：

輸入：nums = [1,2,3,4]
輸出：false
解釋： 
沒有辦法將 nums 分成 4 / 2 = 2 對，使得對滿足每個條件。

限制條件：

• nums.length == 2 * n
• $1 \leq n \leq 500$
• $1 \leq nums[i] \leq 500$

直覺

該問題的挑戰在於將數組劃分為若干對，其中每對包含相同的元素。由於數組的大小總是偶數，直接的推論是，若要實現這樣的劃分，每個元素必須出現偶數次。關鍵的洞察是，只有當每個數字成對出現時，才能夠達成配對。

解法

為了解決這一問題，我們利用 bitset 來有效追蹤每個數字在 nums 數組中出現次數的奇偶性。

1. 初始化：構建一個 bitset，其大小足以處理可能出現在 nums 中的數值索引。鑑於題目的限制，我們使用大小為 501 的 bitset，因為 nums[i] 的範圍是從 1 到 500。

2. 追蹤出現次數：遍歷 nums 數組中的每個整數 num。對於每次出現的 num，翻轉其在 bitset 中對應的位。這種翻轉操作將一個 0 位改為 1（表示奇數次出現）或將 1 位改為 0（表示偶數次出現）。

3. 驗證：處理完所有數字後，檢查 bitset。如果所有元素都可以配對，每個數字應該出現偶數次，這將導致 bitset 中所有位都為零。

4. 返回結果：最後，返回 true，如果 bitset 中設定的位數為零，即表示每個數字都可以完美配對；否則，返回 false。這個條件確保了 nums 數組中每個數字的出現次數都是偶數。

程式碼

C++

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        // 創建一個位元集合來追蹤數字的存在性。
        bitset<501> existence;

        // 遍歷 nums 陣列中的每一個數字。
        for (int num : nums) {
            // 翻轉對應於當前數字的位元。
            existence.flip(num);
        }

        // 如果設置的位元數為0，則表示所有數字都可以配對。
        return (existence.count() == 0);
    }
};

Python

class Solution:
    def divideArray(self, nums):
        # 建立一個集合來追蹤數字的存在。
        existence = set()

        # 遍歷 nums 陣列中的每個數字。
        for num in nums:
            # 如果數字已在集合中，則移除它；否則，新增它。
            if num in existence:
                existence.remove(num)
            else:
                existence.add(num)

        # 如果集合為空，則表示所有數字可以配對。
        return len(existence) == 0

複雜度分析

• 時間複雜度: $O(m)$
  實作過程中需遍歷 nums 陣列，並在一個固定大小的位元集合中翻轉位元。由於對每個元素的操作（翻轉和計數）都是在常數時間內完成，故時間複雜度為 $O(m)$，其中 $m$ 是 nums 中元素的數目。
• 空間複雜度: $O(1)$
  所需空間由 bitset 的大小決定，該大小固定為501位元。不論輸入大小為何，該空間使用量皆保持不變，因此空間複雜度為 $O(1)$。