跳至主要內容

914. 卡牌分组


914. 卡牌分组

🟢   🔖  数组 哈希表 数学 计数 数论  🔗 力扣open in new window LeetCodeopen in new window

题目

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 where x > 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

  1. 使用一个哈希表 Map 统计每个数字在牌中的出现次数。

  2. 计算最大公约数 gcd,最常用高效的办法是 辗转相除法(欧几里得算法)

    • 定理:对于任意两个正整数 ab(假设 a > b),它们的最大公约数等于 ba 除以 b 的余数(a % b)的最大公约数。

    • 形式化表示为:GCD(a, b) = GCD(b, a % b)

    • 算法的步骤如下:

      1. 如果 b = 0,则 GCD(a, b) = a
      2. 否则,递归计算 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
  3. 遍历数组,计算所有数字的频数的最大公约数 gcd

    • 如果 gcd < 2,则返回 false
    • 如果 gcd >= 2,则返回 true

复杂度分析

  • 时间复杂度O(n + m * log(maxCount))
    • 统计数字的频数:O(n),其中 ndeck 数组的长度。
    • 计算最大公约数:O(m * log(maxCount)),其中 m 是不同数字的种类数,maxCount 是最大频数。
  • 空间复杂度O(m),使用了一个哈希表来存储频数。

思路二:枚举法

还可以使用 枚举法,通过枚举可能的 x 来判断是否满足条件。

  1. 统计每张牌的频数
    使用 Map 对牌中的每个数字进行计数,得到每种数字的频数。

  2. 枚举分组的大小 x

    • 遍历从 2n 的所有可能的 xn 是牌的总数)。
    • 如果 x 不能整除 n,直接跳过。
    • 检查每种数字的频数是否能被 x 整除。如果不能,说明不能按当前 x 分组。
  3. 返回结果

    • 如果找到一个满足条件的 x,返回 true
    • 如果所有可能的 x 都不满足条件,返回 false

复杂度分析

  • 时间复杂度O(n * m),其中 ndeck 数组的长度,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;
};