LeetCode 914. 卡牌分组（最大公约数）

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

示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

示例 3：
输入：[1]
输出：false
解释：没有满足要求的分组。

示例 4：
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

示例 5：
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：
1 <= deck.length <= 10000
0 <= deck[i] < 10000

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        if(deck.size() < 2)
        	return false;
        map<int, int> m;
        for(int n : deck)
        	m[n]++;	//统计个数
        if(m.size() == 1)//只有一种
        	return m.begin()->second%2 == 0;//偶数才可以
        int a = m.begin()->second, g;	//g是所有的计数的最大公约数
        map<int, int>::iterator it = ++m.begin();
        for( ; it != m.end(); ++it)
        {
        	g = gcd(a,it->second);
        	a = g;//公约数作为参数a继续求公约数，求出来的是所有计数的最大公约数
        }
        if(g == 1)//最大公约数是1，说明只能1个个的分开，每组个数相等
        	return false;
        return true;
    }

    int gcd(int a, int b)
    {	//求最大公约数
    	int r;
    	while(b != 0)
    	{
    		r= a%b;
    		a = b;
    		b= r;
    	}
    	return a;
    }
};

class Solution {	//2020.3.27
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int,int> map;
        for(auto& d : deck)
            map[d]++;
        int g = 0;
        for(auto& m : map)
        {
            if(g == 0)
                g = m.second;
            else
            {
                g = gcd(g, m.second);
            }
        }
        return g >= 2;
    }

    int gcd(int a, int b)
    {
        int r;
        while(b)
        {
            r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
};