卡牌分组

题目：

给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

• 每组都有 X 张牌。
• 组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

示例：

输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

解题方法：

在完全没有看答案的情况下，我原始的思路是:

• 统计各个数字出现的次数s；
• 找到出现最少的次数minv；
• 计算所有出现次数s是不是能够整除minv，如果能则能够分组；否则则不能。

这个想法失败了，因为minv也能需要分开进行分组，那么minv就要改变。
然后我就想到了最大公约数，但是我不记得计算公式了，所以就有了下面的一段代码：

代码和结果：

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        vector<int> s(10001,0);
        for(int i=0;i<deck.size();i++)
        {
            s[deck[i]]++;
        }

        int minv=100000;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]>0)
            {
                if(minv>s[i])
                    minv=s[i];
            }
        }
        if(minv==1)
            return false;
        for(int i=2;i<=minv;i++)
        {
            int flag=true;
            for(int j=0;j<s.size();j++)
            {
                if(s[j]%i!=0)
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
                return true;
        }
        return false;
    }
};

运行结果:

效果不好，是因为计算最大公约数的过程花费了很多时间，在网上找了一下最大公约数计算方法：

    int gcd(int a,int b)
    {
        return (a%b==0)?b:gcd(b,a%b);
    }

改进了一下代码：

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        if(deck.size()==1)
            return false;
        vector<int> s(10001,0);
        for(int i=0;i<deck.size();i++)
        {
            s[deck[i]]++;
        }

        int mv=-1;
        for(int i=0;i<deck.size();i++)
        {
            if(mv<0)
                mv=s[deck[i]];
            else
                mv=gcd(mv,s[deck[i]]); 
        }
        if(mv==1)
            return false;
        else
            return true;
    }

    int gcd(int a,int b)
    {
        return (a%b==0)?b:gcd(b,a%b);
    }
};

运行结果：

略有提升，但是还是不够理想，内存的消耗比较大，主要是动态开辟数组造成的，需要优化数据结构，至于时间消耗上，可能是多级的索引导致内存不连续读取，还是数据结构用的不太好，不过没什么兴致继续优化了，就这样吧。

原题链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/