914. X of a Kind in a Deck of Cards*

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

题目描述

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 <= deck.length <= 10000
• 0 <= deck[i] < 10000

C++ 实现 1

统计每个元素出现的次数, 之后本质上是求这些次数的最大公约数. (Greatest Common Divisor, GCD).
但我这里是先统计, 然后找其中最小的次数 min_val, 再判断 2 ~ min_val 中有没有能被所有次数整除的值.

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        if (deck.size() < 2) return false;
        unordered_map<int, int> records;
        int min_val = INT32_MAX;
        // 统计次数
        for (auto &a : deck) records[a] ++;
        for (auto &p : records) min_val = std::min(min_val, p.second);
        if (min_val < 2) return false;
        for (int i = 2; i <= min_val; ++ i) {
            int count = 0;
            for (auto &p : records) {
                if (p.second % i != 0) break; // 不能整除就直接 break
                count ++;
            }
            if (count == records.size()) return true; // 说明都能被整除
        }
        return false;
    }
};

C++ 实现 2

C++ 中的 <algorithm> 库提供了 __gcd(a, b) 函数库来求最大公约数 (Greatest Common Divisor, GCD). 代码来自 LeetCode Submission. 关于 __gcd 的介绍可以看:

• std::gcd | C++ inbuilt function for finding GCD
• Euclidean algorithms (Basic and Extended)

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