LeetCode 914: X of a Kind in a Deck of Cards (Frequency GCD Check)
LeetCode 914Hash MapGCDToday we solve LeetCode 914 - X of a Kind in a Deck of Cards.
Source: https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
English
Problem Summary
Given an integer array deck, we need to split all cards into groups of equal size X where X >= 2, and every group contains only identical numbers.
Key Insight
If card values appear with frequencies f1, f2, ..., then one shared group size X is possible iff gcd(f1, f2, ... ) >= 2. So we only need counting + gcd folding.
Algorithm
- Count occurrences of each card value with a hash map.
- Initialize g = 0 and fold all frequencies: g = gcd(g, freq).
- If final g >= 2, return true; otherwise return false.
Complexity Analysis
Time: O(n).
Space: O(k), where k is number of distinct card values.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : deck) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
int g = 0;
for (int f : cnt.values()) {
g = gcd(g, f);
}
return g >= 2;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return Math.abs(a);
}
}func hasGroupsSizeX(deck []int) bool {
cnt := map[int]int{}
for _, x := range deck {
cnt[x]++
}
g := 0
for _, f := range cnt {
g = gcd(g, f)
}
return g >= 2
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> cnt;
for (int x : deck) cnt[x]++;
int g = 0;
for (auto& [_, f] : cnt) {
g = std::gcd(g, f);
}
return g >= 2;
}
};from collections import Counter
from math import gcd
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
cnt = Counter(deck)
g = 0
for f in cnt.values():
g = gcd(g, f)
return g >= 2var hasGroupsSizeX = function(deck) {
const cnt = new Map();
for (const x of deck) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
let g = 0;
for (const f of cnt.values()) {
g = gcd(g, f);
}
return g >= 2;
};
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}中文
题目概述
给定整数数组 deck，需要把所有牌分成若干组，每组大小都为同一个 X（且 X >= 2），并且每组里的牌点数都相同。
核心思路
设不同牌值出现次数为 f1, f2, ...。如果存在统一分组大小 X，那么 X 必须同时整除所有频次；也就是 gcd(f1, f2, ... ) >= 2。因此问题可转化为“所有频次的最大公约数是否至少为 2”。
算法步骤
- 用哈希表统计每个牌值的出现次数。
- 设 g = 0，遍历频次并不断更新 g = gcd(g, freq)。
- 遍历结束后若 g >= 2 返回 true，否则返回 false。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(k)，其中 k 为不同牌值数量。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : deck) {
cnt.put(x, cnt.getOrDefault(x, 0) + 1);
}
int g = 0;
for (int f : cnt.values()) {
g = gcd(g, f);
}
return g >= 2;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return Math.abs(a);
}
}func hasGroupsSizeX(deck []int) bool {
cnt := map[int]int{}
for _, x := range deck {
cnt[x]++
}
g := 0
for _, f := range cnt {
g = gcd(g, f)
}
return g >= 2
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
if a < 0 {
return -a
}
return a
}class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> cnt;
for (int x : deck) cnt[x]++;
int g = 0;
for (auto& [_, f] : cnt) {
g = std::gcd(g, f);
}
return g >= 2;
}
};from collections import Counter
from math import gcd
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
cnt = Counter(deck)
g = 0
for f in cnt.values():
g = gcd(g, f)
return g >= 2var hasGroupsSizeX = function(deck) {
const cnt = new Map();
for (const x of deck) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
let g = 0;
for (const f of cnt.values()) {
g = gcd(g, f);
}
return g >= 2;
};
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
Comments