卡牌分组

来自Leetcode第914题卡牌分组

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

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

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

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

示例 1：

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

求最大公因子

首先遍历数组，将牌上的整数放入对应的桶中，最后遍历桶，如果桶里的计数有最大公因子，就返回真，否则假。

public boolean hasGroupsSizeX(int[] deck) {
    // 计数
    int[] counter = new int[10000];
    for (int num: deck) {
        counter[num]++;
    }
    // 求gcd
    int x = 0;
    for(int cnt: counter) {
        if (cnt > 0) {
            x = gcd(x, cnt);
            if (x == 1) {
                return false;
            }
        }
    }
    return x >= 2;
}

// 辗转相除法
private int gcd (int a, int b) {
    int c;
    while (b > 0){
        c = b % a;
        b = c;
        a = b;
    }
    return a;
}