给定一副牌,每张牌上都写着一个整数。
此时,你需要选定一个数字 X
,使我们可以将整副牌按下述规则分成 1 组或更多组:
- 每组都有
X
张牌。 - 组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2
时返回 true
。
示例 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
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
vals = Counter(deck).values()
return reduce(gcd, vals) >= 2
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] counter = new int[10000];
for (int d : deck) {
++counter[d];
}
int g = -1;
for (int v : counter) {
if (v > 0) {
g = g == -1 ? v : gcd(g, v);
}
}
return g >= 2;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
vector<int> counter(10000);
for (int& d : deck) ++counter[d];
int g = -1;
for (int& v : counter)
if (v > 0)
g = g == -1 ? v : gcd(g, v);
return g >= 2;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};
func hasGroupsSizeX(deck []int) bool {
counter := make([]int, 10000)
for _, d := range deck {
counter[d]++
}
var gcd func(a, b int) int
gcd = func(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
g := -1
for _, v := range counter {
if v > 0 {
if g == -1 {
g = v
} else {
g = gcd(g, v)
}
}
}
return g >= 2
}