914. 卡牌分组 这也是道好题
给定一副牌,每张牌上都写着一个整数。
此时,你需要选定一个数字 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,1,1,1,2,2,2,2,2,2] 时,相当于 1:4 2:6,此时X为2的时候是可以的,也就是说要算,所有数量的共同最小公倍数,且最小公倍数要为X,X要大于等于2了
boolhasGroupsSizeX(vector<int>&deck) {
unordered_map<int, int>res;
for (auto&a : deck) {
res[a] +=1;
}
intminCut= (*(res.begin())).second;
for (autoit=++res.begin(); it!=res.end(); ++it) {
minCut=min(minCut, (*it).second);
}
if (minCut<2) returnfalse;
for (auto&a : res) {
if (a.second%minCut!=0) returnfalse;//这里不能简单的判断当前值是否可以整除最小值
}
returntrue;
}
第二版,改进版本,好题目
执行用时 :16 ms, 在所有 cpp 提交中击败了92.34%的用户
内存消耗 :9.9 MB, 在所有 cpp 提交中击败了73.24%的用户
在运行过程中如果发现最小值小于2或者,当前次数与最小值的最大公约数为1的时候,就该直接返回了
intgreatestCommonDivisor(inta, intb) {
intc=0;
if (a<b) swap(a, b);
while (true) {
c=a%b;
if (c==0) returnb;
else
{
a=b;
b=c;
}
}
}
boolhasGroupsSizeX(vector<int>&deck) {
unordered_map<int, int>res;
for (auto&a : deck) {
res[a] +=1;
}
intminCut= (*(res.begin())).second, greatestCommonDivisoreNum=0;
for (autoit=res.begin(); it!=res.end(); ++it) {
greatestCommonDivisoreNum=greatestCommonDivisor(minCut, it->second);
minCut=min(minCut, (*it).second);
cout<<"leastCommonMultipleNum "<<greatestCommonDivisoreNum<<" minCut "<<minCut<<endl;
if (minCut<2||greatestCommonDivisoreNum==1) returnfalse;
}
returntrue;
}