914.卡牌组合

题目类别
二分查找/随机

题目

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

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

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

思路

1. 给定一个都是整数项的数组，先排序然后看看各数字出现的次数
2. 再判断次数的最大公约数是多少
3. 如果最大公约数是2的倍数，那么就返回true

最大公约数求法利用到了辗转相除法 ，即欧几里得算法

例如求1997和615两个正整数的最大公约数，则：1997/615=3（余152）；615/152=4（余7）；152/7=21（余5）7/5=1（余2）；5/2=2（余1）；2/1=2（余0）

function gcd(a,b) {
  if(a % b === 0) return b;
  return gcd(b,a%b);
}

代码

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {
    //最大公约数计算公式
    function gcd(a,b) {
        if(a%b === 0) return b;
        return gcd(b,a%b)
    }
    //相同的牌出现的次数Map
    let timeMap = new Map()
    deck.forEach(item => {
        timeMap.set(item,timeMap.has(item) ? timeMap.get(item) + 1 : 1);
    });
    let timeArr = [...timeMap.values()];

    //默认数组首位对公约数计算无干扰
    let g = timeArr[0]

    //遍历出现次数，计算最大公约数
    timeArr.forEach(time => {
        g = gcd(g, time);
    })
    return g >=2;
};

其中相同牌出现的次数可以利用reduce方法实现

let timeMap = deck.reduce(function(allDeck, num){
     if(num in allDeck) {
         allDeck[num]++;
     }
     else {
         allDeck[num] = 1;
     }
     return allDeck;
},{})
let timeArr = []
for(let i in timeMap) {
timeArr.push(timeMap[i])
}