leetcode-0914 卡牌分组

[GuoLizhi]

辗转相除法

var hasGroupsSizeX = function(deck) {
    // 计数器，因为题目中已知了deck的长度在10000以内，因此此步骤的空间复杂度为1
    const counter = [];
    for (let i = 0; i < deck.length; i++) {
        counter[deck[i]] = (counter[deck[i]] || 0) + 1;
    }

    // 迭代求出多个数的最大公约数
    let x = 0;
    for (let i = 0; i < counter.length; i++) {
        if (counter[i] > 0) {
            x = gcd(x, counter[i]);
            if (x === 1) {
                return false;
            }
        }
    }
    return x >= 2;
};

// 辗转相除法求最大公约数
var gcd = function(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}