Easy

题目描述

给定一个整数数组 deck，其中 deck[i] 表示第 i 张卡牌上写的数字。

将卡牌分成一个或多个组，使得：

  • 每组恰好有 x 张卡牌，其中 x > 1
  • 一组内的所有卡牌上都写着相同的整数

如果可能分组，返回 true；否则返回 false。

示例 1：

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

示例 2：

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

提示：

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

解题思路

解题思路

这道题的核心在于理解题目要求：每个数字的卡牌都要分成大小相同的组，且组的大小必须大于1。

关键观察：

  1. 如果存在满足条件的分组方案，那么每个数字出现的次数都必须能被同一个数 x（x > 1）整除
  2. 换句话说，所有数字出现次数的最大公约数（GCD）必须大于1

解法一：最大公约数法（推荐）

  1. 统计每个数字出现的次数
  2. 求出所有次数的最大公约数
  3. 判断最大公约数是否大于1

解法二：暴力枚举法 枚举可能的组大小 x（从2到最小出现次数），检查是否所有次数都能被 x 整除。

算法步骤：

  1. 使用哈希表统计每个数字的出现次数
  2. 计算所有出现次数的最大公约数
  3. 返回最大公约数是否大于1

时间复杂度主要取决于计算GCD的过程，空间复杂度为统计频次所需的空间。

代码实现

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

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        from collections import Counter
        import math
        
        count = Counter(deck)
        gcd_result = 0
        
        for freq in count.values():
            gcd_result = math.gcd(gcd_result, freq)
        
        return gcd_result >= 2

public class Solution {
    public bool HasGroupsSizeX(int[] deck) {
        var count = new Dictionary<int, int>();
        foreach (int card in deck) {
            count[card] = count.GetValueOrDefault(card, 0) + 1;
        }
        
        int gcdResult = 0;
        foreach (var freq in count.Values) {
            gcdResult = GCD(gcdResult, freq);
        }
        
        return gcdResult >= 2;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var hasGroupsSizeX = function(deck) {
    const count = {};
    for (const card of deck) {
        count[card] = (count[card] || 0) + 1;
    }
    
    const gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    
    let gcdResult = 0;
    for (const freq of Object.values(count)) {
        gcdResult = gcd(gcdResult, freq);
    }
    
    return gcdResult >= 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k·log(min(freq)))n为卡牌数量，k为不同数字种类，log项为计算GCD的复杂度
空间复杂度O(k)k为不同数字的种类数，用于存储频次统计