EasyRating 1371

914. X of a Kind in a Deck of Cards

arrayhash-tablemathcountingnumber-theory

在 LeetCode 上作答 ↗

解題說明

X of a Kind in a Deck of Cards

題目描述：給定一副牌 deck，每張牌上有一個數字。能否將所有牌分成若干組，每組恰好 x 張（x >= 2），且同一組中所有牌的數字相同？

解題思路：

統計 + GCD：先統計每個數字出現的次數。
問題轉化為：是否存在 x >= 2，使得所有次數都能被 x 整除。
這等價於所有次數的最大公因數 (GCD) >= 2。
因為如果 GCD = g >= 2，我們可以取 x = g，每個數字出現 count[i] 次，分成 count[i] / g 組，每組 g 張。
如果 GCD = 1，則不存在 x >= 2 能整除所有次數。

C++ 解法

複雜度分析

時間複雜度：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 等價，但實作更複雜。

延伸思考

如果每組不一定要大小相同（只要每組 >= 2 且同一數字），問題是否永遠可行？
如果要求 x 為質數，答案會有什麼變化？
如何找出所有可行的 x 值？

X of a Kind in a Deck of Cards — CaffeCode