题目描述

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

• 每组都有 X 张牌。
• 组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

样例

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

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

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

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

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

注意

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

算法

(最大公约数) $O(n \log^2 n)$

1. 首先将数组从小到大排序，然后将每一段相同数字的长度存放到数组 num 中。
2. 然后求 num 中所有长度的最大公约数，如果最大公约数大于 1，则返回 true。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，求两个数的最大公约数的时间复杂度为 $O(log^2 C)$。
• 由于每个数不超过 $n$，总时间复杂度为 $O(n \log^2 n)$。

空间复杂度

• 需要一个额外的数组存放所有长度，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:

    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    bool hasGroupsSizeX(vector<int>& deck) {
        int n = deck.size();
        vector<int> num;

        sort(deck.begin(), deck.end());
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (deck[i] != deck[i - 1]) {
                num.push_back(cnt);
                cnt = 1;
            }
            else
                cnt++;
        }
        num.push_back(cnt);

        int ans = num[0];
        for (int i = 1; i < num.size(); i++)
            ans = gcd(ans, num[i]);

        return ans > 1;
    }
};