914. X of a Kind in a Deck of Cards(Leetcode每日一题-2020.03.27)

Problem

In a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards.
All the cards in each group have the same integer.

Example1

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].

Example2

Input: deck = [1,1,1,2,2,2,3,3]
Output: false´
Explanation: No possible partition.

Example3

Input: deck = [1]
Output: false
Explanation: No possible partition.

Example4

Input: deck = [1,1]
Output: true
Explanation: Possible partition [1,1].

Example5

Input: deck = [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2].

Solution

选一个X>=2的数，将牌分成N堆，每堆X张牌，且每堆牌都是一样的数字。
返回一个牌堆是否可以按照上述方式分堆。

首先，空的或只有一张牌的牌堆肯定不行。
其次，统计排队中每种牌的数量后，如果存在只有一张的情况，肯定也不行。
最后，计算每种牌数量的最大公约数，如果最大公约数大于等于而，那么就是可以的。

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        if(deck.size() <= 1)
            return false;
        
        int count[10000] = {0};
        for(auto d:deck)
            count[d]++;
        
        int gcd_val = 0;
        for(int i = 0;i<10000;++i)
        {
            if(count[i] == 1)
                return false;
            if(count[i] != 0)
                gcd_val = gcd(count[i],gcd_val);
        }

        return gcd_val >=2;

    }

    int gcd(int a,int b)
    {
        if(a < b)
            return gcd(b,a);
        if(b == 0)
            return a;
        return gcd(b,a%b);
    }
};