本文主要是介绍914. X of a Kind in a Deck of Cards,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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
解法一
//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:int maxCommonFactor(int a, int b) {//a >= bint mod = -1;while(mod != 0) {mod = a % b;if(mod == 0) return b;a = b;b = mod;}return 0;}bool hasGroupsSizeX(vector<int>& deck) {unordered_map<int, int> um;for(int num : deck) um[num]++;//计数int minCount = INT_MAX;for(auto p : um) minCount = min(minCount, p.second);//求最小计数if(minCount < 2) return false;for(auto p : um) {if(maxCommonFactor(p.second, minCount) < 2) return false;}return true;}
};
思路:
- 使用一个map对每个数字计数;
- 找出map中计数最小的计数值minCount;
- 遍历其它所有数字的计数值,如果有任何一个计数值与minCount的最大公因数小于2,就返回false。否则返回true。
- 求最大公因数使用了辗转相除法(条件a >= b)。
2019/08/5 00:04
这篇关于914. X of a Kind in a Deck of Cards的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!