914. 卡牌分组

题目来源：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards

题目

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

此时，你需要选定一个数字 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

解题思路

思路：求最大公约数。

审题，分析题意：

• 相同整数的牌放在同一组
• 每组的牌都是 X 张

这里首先想到的是统计元素，对照示例 1，示例 2，统计元素个数，元素个数相等可以分组成功返回 True，否则返回 False，这是一个思路。

再看示例 3，如果组内的元素只有 1 个的时候，直接返回 False。

再看示例 5，这里 1 的个数为 2 个， 2 的个数为 4 个。这里将原组 [2,2,2,2] 分成两组 [2,2]，这样与前面 [1,1] 的元素个数就相同了。

针对示例 5，1 有 2 个，2 有 4 个，最终分组元素个数都是 2个，其实这里 X = 2，是这两个组元素个数的公约数。

根据上面结合题意与示例的分析，确定以下思路：

• 首先遍历统计元素个数，如果某个元素只有一个，直接返回 False；
• 考虑示例 5 的情况 ，拆分相同元素的组进而达到符合题意的分组。这里面涉及到公约数的思想，同时分组后组内的元素个数严格大于 1，那么可以考虑求最大公约数，同时确保最大公约数大于 1。

代码实现

from typing import List

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        # 用以统计元素个数
        from collections import Counter
        import math
        from functools import reduce
        
        # 计算元素的个数
        cnt_values = Counter(deck).values()
        # reduce() 对参数序列中的元素进行累积
        # 先对第 1，2 个元素进行操作，结果与第 3 个元素进行计算，以此类推
        return reduce(math.gcd, cnt_values) > 1

实现效果

以上就是通过统计元素个数，进而求最大公约数，并且在约束条件最大公约数严格大于 1 下，得出结果解决《卡牌分组》问题的主要内容。