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 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，最常用高效的办法是 辗转相除法（欧几里得算法）

   • 定理：对于任意两个正整数 a 和 b（假设 a > b），它们的最大公约数等于 b 和 a 除以 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)，其中 n 是 deck 数组的长度。
  • 计算最大公约数：O(m * log(maxCount))，其中 m 是不同数字的种类数，maxCount 是最大频数。
• 空间复杂度：O(m)，使用了一个哈希表来存储频数。

---

思路二：枚举法

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

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

2. 枚举分组的大小 x

   • 遍历从 2 到 n 的所有可能的 x（n 是牌的总数）。
   • 如果 x 不能整除 n，直接跳过。
   • 检查每种数字的频数是否能被 x 整除。如果不能，说明不能按当前 x 分组。

3. 返回结果

   • 如果找到一个满足条件的 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;
};