【Leetcode】914. 卡牌分组

矫情吗；* 2022-11-19 11:12 207阅读 0赞

### 文章目录 ###

*   *   *  【题目】
         *  【题目分析】
         *  【代码实践】

### 【题目】 ###

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

每组都有 X 张牌。  
组内所有的牌上都写着相同的整数。  
仅当你可选的 X >= 2 时返回 true。

示例 1：

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

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

示例 3：

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

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

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

提示：

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

### 【题目分析】 ###

1：根据题目的描述，很明确的一点是需要统计牌面数值的出现次数  
2：如何分析合适的每组张数  
3：每组是有一定的关联，数量相同，但是不限制某个数字的数量被分成了多个组  
4：每种数字的数量必须是X的倍数，根据这样的描述可以转换为每种数字张数的最大公约数

### 【代码实践】 ###

1：选择一个合适的数据结构存储计数，如果使用数组的话，那么考虑到大的边界值那么需要创建过大的数组容量，这里选择使用Map  
2：通过辗转相除法计数最大公约数  
3：只要最大公约数满足大于等于2,即X大于等于2即可

public boolean hasGroupsSizeX(int[] deck) { 
            //计数统计
            Map<Integer, Integer> timeMap = new HashMap<>();
            for (int key : deck) { 
                timeMap.put(key, timeMap.containsKey(key) ? timeMap.get(key) + 1 : 1);
            }
            //求最大公约数
            int res = 0;
            for (Map.Entry<Integer, Integer> entry : timeMap.entrySet()) { 
                res = gcd(entry.getValue(), res);
            }
            return res >= 2;
        }
    
        public int gcd(int num1, int num2) { 
            // 利用辗转相除法来计算最大公约数
            return num2 == 0 ? num1 : gcd(num2, num1 % num2);
        }