---

卡牌分组

归类运算

914. 卡牌分组 - 力扣（LeetCode）

1.题目

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：[1]
输出：false
解释：没有满足要求的分组。

示例 4：

输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

示例 5：

输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：

• 1 <= deck.length <= 10000
• 0 <= deck[i] < 10000

测试用例

// [1, 1, 1, 2, 2, 2, 3, 3]
// [1, 1, 1, 1, 2, 2, 2, 2, 2, 2]
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3,
//     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8]

2.思路分析

元素的个数组成一个数组，数组元素最大公约数大于1即可

3.所用到的方法

求元素的个数并组成一个数组

Array.reduce

let counts = Object.values(
  deck.reduce((arr, index) => {
    arr[index] = arr[index] + 1 || 1
    return arr
  }, {})
)

Array.forEach

let tmp = {}
deck.forEach(item => {
  tmp[item] = tmp[item] ? tmp[item] + 1 : 1
})
let counts = Object.values(tmp)

求最大公约数

// 两数求最大公约数
let gcd = (pre, cur) => {
  return cur === 0 ? pre : gcd(cur, pre % cur)
}
// 多个数需要转为数组并搭配循环使用
arr.forEach(item => {
  arr[0] = gcd(arr[0], item)
})
console.log(arr[0]) // 这就是最大公约数

4.题解及优化

我的题解

var hasGroupsSizeX = function (deck) {
  // 查找每种元素的个数组成一个数组
  let counts = Object.values(
    deck.reduce((arr, index) => {
      arr[index] = arr[index] + 1 || 1
      return arr
    }, {})
  )

  // 利用辗转相除法来计算最大公约数
  let gcd = (pre, cur) => {
    return cur === 0 ? pre : gcd(cur, pre % cur)
  }
  // 每两项之间求最大公约数，并把结果保存到数组第一项来与下一项进行运算
  counts.forEach(item => {
    counts[0] = gcd(counts[0], item)
  })

  // 这个数组的最小公因数存在且大于1即true
  return counts[0] > 1
}

修改reduce为forEach

var hasGroupsSizeX = function(deck) {
  // 查找每种元素的个数组成一个数组
  let tmp = {} // 临时变量
  deck.forEach(item => {
    tmp[item] = tmp[item] ? tmp[item] + 1 : 1
  })
  let counts = Object.values(tmp)

  // 利用辗转相除法来计算最大公约数
  let gcd = (pre, cur) => {
    return cur === 0 ? pre : gcd(cur, pre % cur)
  }
  // 每两项之间求最大公约数，并把结果保存到数组第一项来与下一项进行运算
  counts.forEach(item => {
    counts[0] = gcd(counts[0], item)
  })

  // 这个数组的最小公因数存在且大于1即true
  return counts[0] > 1
}

---

课程解法

var hasGroupsSizeX = function (deck) {
  // 存储每张卡牌的总数
  // 修改排序的方式修改为直接统计每个相同字符的数量，思路不变（LeetCode测试用例）
  let group = []
  let tmp = {}
  deck.forEach(item => {
    tmp[item] = tmp[item] ? tmp[item] + 1 : 1
  })
  for (let v of Object.values(tmp)) {
    group.push(v)
  }
  // 此时group已经存放的是每张牌的总数了（数组只遍历一遍，避免了排序和正则的耗时）
  // 求两个数的最大公约数
  let gcd = (a, b) => {
    if (b === 0) {
      return a
    } else {
      return gcd(b, a % b)
    }
  }
  while (group.length > 1) {
    let a = group.shift()
    let b = group.shift()
    let v = gcd(a, b)
    if (v === 1) {
      return false
    } else {
      group.unshift(v)
    }
  }
  return group.length ? group[0] > 1 : false
}

---

其他小伙伴的解法

var hasGroupsSizeX = function(deck) {
    // 最大公约数计算公式
    function gcd(num1, num2) {
        // 利用辗转相除法来计算最大公约数
        return num2 === 0 ? num1 : gcd(num2, num1 % num2); 
    }

    // 相同牌出现次数Map
    let timeMap = new Map();

    // 遍历牌
    deck.forEach(num => {
        // 统计每张牌出现的次数
        timeMap.set(num, timeMap.has(num) ? timeMap.get(num) + 1 : 1);
    });

    // Map.protype.values()返回的是一个新的Iterator对象，所以可以使用扩展运算符(...)来构造成数组
    let timeAry = [...timeMap.values()];

    /*
    最大公约数
    因为该数组是出现次数数组，最小值至少为1（至少出现1次），所以默认赋值为数组首位对公约数计算无干扰
    */
    let g = timeAry[0];

    // 遍历出现次数，计算最大公约数
    timeAry.forEach(time => {
        // 因为需要比较所有牌出现次数的最大公约数，故需要一个中间值
        g = gcd(g, time);
    });

    // 判断是否满足题意
    return g >= 2;
}

---

最简解法

var hasGroupsSizeX = function(deck) {
  let t = {}
  deck.forEach(i => { t[i] = t[i] ? t[i] + 1 : 1 })
  let arr = Object.values(t)
  let gcd = (a, b) => (b === 0 ? a : gcd(b, a % b))
  return arr.every(i => (arr[0] = gcd(arr[0], i)) > 1)
}

这里使用了Array.every来检测数组经过求最大公约数后的每一项是否符合要求，只要有一项不符合就直接返回false，这样节省了一部分时间