914.卡牌分组

链接：914.卡牌分组
难度：Easy
标签：数组、哈希表、数学、计数、数论
简介：给定一副牌，每张牌上都写着一个整数。此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：每组都有  X  张牌。组内所有的牌上都写着相同的整数。仅当你可选的 X >= 2 时返回  true。

题解 1 - cpp

• 编辑时间：2022-01-07
• 执行用时：4ms
• 内存消耗：17MB
• 编程语言：cpp
• 解法介绍：求所有数出现的次数最大公约数是否大于等于 2。

class Solution {
   public:
    int gcd(int a, int b) {
        if (b) return gcd(b, a % b);
        return a;
    }
    bool hasGroupsSizeX(vector<int> &deck) {
        map<int, int> m;
        int ans = -1;
        for (auto &num : deck) m[num]++;
        for (auto &num : m) {
            if (ans == -1)
                ans = num.second;
            else
                ans = gcd(ans, num.second);
            if (ans == 1) break;
        }
        return ans >= 2;
    }
};