class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
}
};
914. 卡牌分组
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 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 <= 1040 <= deck[i] < 104原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 5.4 MB, 提交时间: 2023-09-27 16:32:25
func hasGroupsSizeX(deck []int) bool {
if len(deck)==0{
return false
}
m := make(map[int]int)
for _,v:=range deck{
m[v]++
}
maxVal := m[deck[0]]
for _,v:=range m{
maxVal= gcd(v,maxVal)
if maxVal<2 {
return false
}
}
return true
}
func gcd(x, y int) int {
tmp := x % y
if tmp > 0 {
return gcd(y, tmp)
} else {
return y
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 17.3 MB, 提交时间: 2023-09-27 16:31:32
class Solution {
int cnt[10000];
public:
bool hasGroupsSizeX(vector<int>& deck) {
for (auto x: deck) cnt[x]++;
int g = -1;
for (int i = 0; i < 10000; ++i) {
if (cnt[i]) {
if (~g) {
g = gcd(g, cnt[i]);
} else {
g = cnt[i];
}
}
}
return g >= 2;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 42.6 MB, 提交时间: 2023-09-27 16:31:20
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
for (int c: deck) {
count[c]++;
}
int g = -1;
for (int i = 0; i < 10000; ++i) {
if (count[i] > 0) {
if (g == -1) {
g = count[i];
} else {
g = gcd(g, count[i]);
}
}
}
return g >= 2;
}
public int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-07-28 15:32:32
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
vals = collections.Counter(deck).values()
return reduce(gcd, vals) >= 2
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-07-28 15:31:46
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
count = collections.Counter(deck)
N = len(deck)
for X in range(2, N + 1):
if N % X == 0:
if all(v % X == 0 for v in count.values()):
return True
return False