【leetcode】914. 卡牌分组（x-of-a-kind-in-a-deck-of-cards）（数学）[简单]

链接

https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/

耗时

解题：33 min
题解：11 min

题意

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

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

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

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

思路

仔细分析两条规则不难发现分牌时只需考虑每种牌的数量，不需要考虑牌的具体数字。

结合上述思考再分析规则，可以发现根据规则，每种牌的数量必须能整除 X，那么也就是说所有种牌的数量的最大公约数就是最大的 X。

那么思路就是求出所有种牌的数量的 gcd，检查 gcd 是否 $\ge 2$ 即可。

AC代码

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        int cnt[10100] = {0};
        for(auto x:deck) {
            cnt[x]++;
        }
        int i = 0, ans;
        for(; i < 10000; ++i) {
            if(cnt[i]) {
                ans = cnt[i];
                break;
            }
        }
        for(;i < 10000; ++i) {
            if(cnt[i]) {
                ans = __gcd(ans, cnt[i]);
                if(ans == 1) return false;
            }
        }
        return ans >= 2;
    }
};