[每日 LeetCode] 914. X of a Kind in a Deck of Cards

原文链接 [每日 LeetCode] 914. X of a Kind in a Deck of Cards

Description:

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.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: [1,1]
Output: true 
Explanation: Possible partition [1,1]

Example 5:

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

Note:

1. 1 <= deck.length <= 10000
2. 0 <= deck[i] < 10000

思路：使用 map 结构记录数组中每个元素出现的次数，该题转化为求次数的最大公约数，若所有次数的最大公约数大于或者等于 2，返回 true，否则返回 false。

我的 C++ 代码

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> nums;
        int res = 0;
        for(auto &n : deck)
            nums[n]++;
       
        for(auto num : nums){
            res = __gcd(num.second,res);
        }
        return res > 1;
    }
};

注：此解使用了 C++17 中求最大公约数的函数__gcd，可用自行设计的 gcd 函数求解。

运行时间：16ms
运行内存：10.2M