914.卡牌分组

914.卡牌分组

Category	Difficulty	Likes	Dislikes
algorithms	Easy (38.31%)	261	-

Tags
Companies
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 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 <= 104
• 0 <= deck[i] < 104

---

Discussion | Solution

思路

判断数组长度，如果大于 2，且为素数说明一定不可能平分，直接剪枝返回 false。遍历一次数组，记录可以平分的可能性，且使用 map 存储各个数出现的次数。再逐个判断可以平分的可能性，判断各个数出现的次数是否都能整除，每个元素的出现的次数都能整数才返回 true。

解答

/*
 * @lc app=leetcode.cn id=914 lang=javascript
 *
 * [914] 卡牌分组
 */

// @lc code=start

const isPrime = (num) => {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
};

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function (deck) {
  // 素数长度，一定不能等分，提前剪枝
  if (deck.length > 2 && isPrime(deck.length)) return false;

  const arr = [];
  let map = {};

  for (let i = 0; i <= deck.length; i++) {
    const num = deck[i];
    if (num && map[num]) map[num]++;
    else if (num) map[num] = 1;

    if (i >= 2 && deck.length % i === 0) arr.push(i);
  }

  map = [...Object.values(map)];

  for (const count of arr) {
    if (map.every((num) => num % count === 0)) return true;
  }

  return false;
};
// @lc code=end