题目描述
给定一副牌,每张牌上都写着一个整数。
此时,你需要选定一个数字 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]
解法
由题目可知,若每组为 x
个数字,则需要将数组 arr
分为 len(arr)/x
个分组,每个分组内数字相同。
若已知每个数字对应出现的次数 cnt_i
,则只需要找到一个数字 s
,使得对于每个 cnt_i
都能整除 s
。
代码语言:javascript复制不妨由最小的次数
cnt_min
开始计算,不断降低s
,判断是否可以被所有cnt_i
整除。
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
countset=set(collections.Counter(deck).values())
minv=min(countset)
if minv==1:
return False
i=1
while i<=(minv//2):
for v in countset:
if v%(minv//i):
i =1
break
else:
return True
return False