leetcode-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 <= 100000 <= deck[i] < 10000
要完成的函数：
bool hasGroupsSizeX(vector<int>& deck)
说明：
1、这道题给定一个vector，vector中存放着卡牌的数字，比如1、2、3、4这样子，你需要把这些卡牌分成多组。
要求同一组中的卡牌数字一致，并且每一组中的卡牌张数一样。
比如123321，你就可以分成[1,1]，[2,2]，[3,3]。
如果可以这样分组，并且组中卡牌张数大于等于2，那么返回true，否则返回false。
限制卡牌数字在[0,10000)，vector中的卡牌张数在[1,10000]。
2、我们最开始可以用vector也可以用map，来存放各个数字的卡牌各有多少张。
（笔者一开始的错误想法：这里用先排序后遍历的做法，有点傻，因为排序O(nlogn)的时间复杂度太高了，还不如直接遍历。）
得到各个数字卡牌的张数之后，我们需要看一下是否可以分组。
这里有个地方要注意下，比如卡牌1有4张，卡牌2有6张，是否可以分组呢？
可以的，每组2张就可以了，卡牌1有2组，卡牌2有3组。
也就是说，我们要求各种数字卡牌的张数的最大公约数，看一下最大公约数是否大于等于2。
而不能简单地看各种数字卡牌的张数是否一致。
但是求集体的最大公约数太麻烦了，还不如直接从2开始，判断所有数字可不可以整除2。
如果可以，那么返回true。如果不行，看一下是否可以整除3……
继续判断，一直到最小的张数。
代码如下：（附详解）
bool hasGroupsSizeX(vector<int>& deck)
{
unordered_map<int,int>m1;//用不排序的map来记录，节省排序的时间
for(int i:deck)//把每种卡牌的张数记录在map中
m1[i]++;
bool flag;
int min1=INT_MAX;//min1用来存放最小的张数
for(unordered_map<int,int>::iterator iter=m1.begin();iter!=m1.end();iter++)
min1=min(min1,iter->second);
for(int i=2;i<=min1;i++)//从2开始判断，一直到最小的张数
{
flag=0;
for(unordered_map<int,int>::iterator iter=m1.begin();iter!=m1.end();iter++)//遍历map，判断张数能不能整除2、3、4……
{
if(iter->second%i!=0)//如果不能整除，那么break出去，换下一个整数继续遍历判断
{
flag=1;
break;
}
}
if(flag==0)//如果遍历了一遍，都可以整除，那么返回true
return true;
}
return false;//如果尝试了各种数字，都不能整除，那么返回false。
}上述代码实测8ms，beats 99.48% of cpp submissions。
这道题的一个启示是：如果要求很多数字的集体公约数，可以从2开始，逐个（可以的话用质数，更快）判断能不能整除，如果某个数字大家都能整除，那么就是集体公约数。
笔者最开始的想法是用辗转相除法求出前两个数的最大公约数a，接着再求第二个数和第三个数的最大公约数b，然后求a和b的最大公约数，记为a，
接着再求第三个数和第四个数的最大公约数b，然后求a和b的最大公约数，记为a……
不断循环下去，求得所有数的最大公约数，看会不会大于等于2。
这样做似乎也可以，但是有点麻烦，之后可以尝试一下。
腾讯云开发者
