914. 卡牌分组
914. 卡牌分组
🟢 🔖 数组
哈希表
数学
计数
数论
🔗 力扣
LeetCode
题目
You are given an integer array deck
where deck[i]
represents the number written on the ith
card.
Partition the cards into one or more groups such that:
- Each group has exactly
x
cards wherex > 1
, and - All the cards in one group have the same integer written on them.
Return true
if such partition is possible, orfalse
otherwise.
Example 1:
Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation : Possible partition [1,1],[2,2],[3,3],[4,4].
Example 2:
Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation : No possible partition.
Constraints:
1 <= deck.length <= 10^4
0 <= deck[i] < 10^4
题目大意
给定一副牌,每张牌上都写着一个整数。
此时,你需要选定一个数字 X
,使我们可以将整副牌按下述规则分成 1 组或更多组:
- 每组都有
X
张牌。 - 组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2
时返回 true
。
示例 1:
输入: deck = [1,2,3,4,4,3,2,1]
输出: true
解释: 可行的分组是 [1,1],[2,2],[3,3],[4,4]
示例 2:
输入: deck = [1,1,1,2,2,2,3,3]
输出: false
解释: 没有满足要求的分组。
提示:
1 <= deck.length <= 10^4
0 <= deck[i] < 10^4
解题思路
思路一:最大公约数法
要判断能否将整副牌分成满足条件的组,关键在于找到一个满足所有数字频数的 最大公约数 (GCD),并确保这个最大公约数 X >= 2
。
使用一个哈希表
Map
统计每个数字在牌中的出现次数。计算最大公约数
gcd
,最常用高效的办法是 辗转相除法(欧几里得算法)定理:对于任意两个正整数
a
和b
(假设a > b
),它们的最大公约数等于b
和a
除以b
的余数(a % b
)的最大公约数。形式化表示为:
GCD(a, b) = GCD(b, a % b)
算法的步骤如下:
- 如果
b = 0
,则GCD(a, b) = a
。 - 否则,递归计算
GCD(b, a % b)
。
- 如果
举例来说,假设我们要计算
GCD(48, 18)
:GCD(48, 18)
48 % 18 = 12
- 现在计算
GCD(18, 12)
18 % 12 = 6
- 现在计算
GCD(12, 6)
12 % 6 = 0
- 现在计算
GCD(6, 0)
,结果为6
- 最终,
GCD(48, 18)
的结果是6
遍历数组,计算所有数字的频数的最大公约数
gcd
。- 如果
gcd < 2
,则返回false
。 - 如果
gcd >= 2
,则返回true
。
- 如果
复杂度分析
- 时间复杂度:
O(n + m * log(maxCount))
- 统计数字的频数:
O(n)
,其中n
是deck
数组的长度。 - 计算最大公约数:
O(m * log(maxCount))
,其中m
是不同数字的种类数,maxCount
是最大频数。
- 统计数字的频数:
- 空间复杂度:
O(m)
,使用了一个哈希表来存储频数。
思路二:枚举法
还可以使用 枚举法,通过枚举可能的 x
来判断是否满足条件。
统计每张牌的频数
使用Map
对牌中的每个数字进行计数,得到每种数字的频数。枚举分组的大小
x
- 遍历从
2
到n
的所有可能的x
(n
是牌的总数)。 - 如果
x
不能整除n
,直接跳过。 - 检查每种数字的频数是否能被
x
整除。如果不能,说明不能按当前x
分组。
- 遍历从
返回结果
- 如果找到一个满足条件的
x
,返回true
。 - 如果所有可能的
x
都不满足条件,返回false
。
- 如果找到一个满足条件的
复杂度分析
- 时间复杂度:
O(n * m)
,其中n
是deck
数组的长度,m
是不同数字的种类数。- 统计数字的频数:
O(n)
。 - 枚举
x
的循环次数最多为n
,每次需要检查所有m
个频数,复杂度为O(n * m)
。
- 统计数字的频数:
- 空间复杂度:
O(m)
,使用了一个哈希表来存储频数。
代码
/**
* @param {number[]} deck
* @return {boolean}
*/
var hasGroupsSizeX = function (deck) {
const count = new Map();
// 统计频数
for (let card of deck) {
count.set(card, (count.get(card) || 0) + 1);
}
// 求最大公约数的辅助函数
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
// 所有频数的数组
const counts = Array.from(count.values());
let g = counts[0];
// 依次计算所有频数的最大公约数
for (let freq of counts) {
g = gcd(g, freq);
if (g === 1) return false; // 一旦 gcd 为 1,直接返回 false
}
return g >= 2;
};
/**
* @param {number[]} deck
* @return {boolean}
*/
var hasGroupsSizeX = function (deck) {
let map = new Map();
for (let num of deck) {
map.set(num, (map.get(num) || 0) + 1);
}
const n = deck.length;
for (let x = 2; x <= n; x++) {
let flag = true;
if (n % x == 0) {
for (let value of map.values()) {
if (value % x !== 0) {
flag = false;
break;
}
}
if (flag) return true;
}
}
return false;
};