題目描述: 給定一副牌 deck,每張牌上有一個數字。能否將所有牌分成若干組,每組恰好 x 張(x >= 2),且同一組中所有牌的數字相同?
解題思路:
時間複雜度:O(n log C) — n 為牌數,C 為最大計數值。統計 O(n),GCD 計算 O(k log C),k 為不同數字數量
空間複雜度:O(k) — k 為不同數字的數量
1. Count frequency of each card value using hash map 2. Compute GCD of all frequencies: a. Initialize g = 0 b. For each frequency cnt: g = gcd(g, cnt) 3. Return g >= 2
枚舉 x 值:從 x = 2 開始枚舉到最小計數值。對每個 x,檢查是否所有計數都能被 x 整除。時間複雜度 O(n + k * max_count)。雖然正確但不如 GCD 方法優雅。
質因數分解:找到所有計數的公共質因數,任何一個 >= 2 的公共因數都可作為 x。本質上與 GCD 等價,但實作更複雜。