TNotes.leetcode

Appearance

0914. 卡牌分组【简单】

0914. 卡牌分组【简单】 ​

1. 📝 题目描述 ​

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

  • 每组都有 X 张牌
  • 组内所有的牌上都写着相同的整数

仅当你可选的 X >= 2 时返回 true。

示例 1：

txt
输入：deck = [1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

txt
输入：deck = [1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

提示：

  • 1 <= deck.length <= 10^4
  • 0 <= deck[i] < 10^4

2. 🎯 s.1 - 暴力解法 - 查询所有可能的分组情况 ​

js
/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function (deck) {
  // 边界条件
  if (deck.length < 2) return false

  // 步骤1：统计每个数字的出现次数
  const cnt = new Map()
  for (const x of deck) {
    cnt.set(x, (cnt.get(x) || 0) + 1)
  }

  const counts = Array.from(cnt.values())
  const minCount = Math.min(...counts)

  // 步骤2：如果最小出现次数 < 2，肯定无法分组
  if (minCount < 2) return false

  // 步骤3：枚举所有可能的分组大小 X（从2到minCount）
  for (let X = 2; X <= minCount; X++) {
    let canDivide = true

    // 检查每个数字的数量是否能被X整除
    for (const c of counts) {
      if (c % X !== 0) {
        canDivide = false
        break
      }
    }

    if (canDivide) {
      return true // 找到了合适的分组大小
    }
  }

  return false // 没有找到合适的分组大小
}
  • 时间复杂度：O(k⋅M)，其中 k 为不同牌值个数，M=min(counts)
    • 最坏情况下 M 可达 O(n)，整体最坏为 O(n2)
  • 空间复杂度：O(k)，用于频次统计

算法思路：

  • 先用哈希表统计每个数字的出现次数，得到计数数组 counts
  • 枚举可能的分组大小 X，范围为 [2, min(counts)]
  • 对每个 X 检查所有计数 c 是否满足 c % X == 0，若全部满足则可行，返回 true
  • 若所有 X 均不满足则返回 false；

该方法直观但在最坏情况下复杂度较高，优化可用“计数 + GCD”（见 s.2）

3. 🎯 s.2 - 计数 + 最大公约数（GCD） ​

js
/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function (deck) {
  // 边界条件：至少需要 2 张牌才能分组
  if (deck.length < 2) return false

  // 计数每个数字的出现次数
  const cnt = new Map()
  for (const x of deck) cnt.set(x, (cnt.get(x) || 0) + 1)

  // 计算所有计数的最大公约数
  let g = 0
  for (const c of cnt.values()) {
    g = gcd(g, c)
    if (g === 1) return false // 剪枝：一旦公约数为 1，则无法分组
  }
  return g >= 2
}

// 欧几里得算法求最大公约数
function gcd(a, b) {
  while (b !== 0) {
    const t = a % b
    a = b
    b = t
  }
  return Math.abs(a)
}
  • 时间复杂度：O(n)，统计频次并计算所有计数的 GCD
  • 空间复杂度：O(k)，k 为不同牌值的个数（使用哈希表计数）

算法思路：

  • 先用哈希表统计每个数字的出现次数
  • 若所有计数的最大公约数满足 gcd(c₁, c₂, ..., cₙ) ≥ 2，则可按 X = gcd 将每类牌平分为若干组
  • 一旦公约数变为 1，即无法满足分组条件，直接返回 false

Discussions