Leetcode_Array --914. X of a Kind in a Deck of Cards [easy]

In a deck of cards, each card has an integer written on it.
在一副扑克牌中，每张牌上都写了一个整数
Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:
Each group has exactly X cards.
All the cards in each group have the same integer.

如果你能且仅能找到一个 X>= 2，使这些牌分成一组或多组牌，这些牌满足如下规则：
每组牌都恰好含有X张卡片
每组卡片中的数都相同
那么返回 true

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:
1、1 <= deck.length <= 10000
2、0 <= deck[i] < 10000

Solution：
这个算法是要统计deck中所有元素出现的个数，元素出现个数中最小的个数为整个元素出现个数列表中的最大公约数，也就是说分成的组的元素个数最小从2开始，最大就到这个最大公约数。这样我们就需要先统计元素出现个数，再找到deck中所有元素出现个数的最大公约数，然后遍历从2到这个最大公约数，如果元素出现的个数对这个区间的某个数a求余都为0，表示可以按照a进行分组，每组元素个数为a，返回true，如果找不到这个a，则返回false。

Python

from collections import Counter
class Solution:
    def hasGroupsSizeX(self, deck):
        """
        :type deck: List[int]
        :rtype: bool
        """
        count = set(list(Counter(deck).values()))   #统计deck元素出现个数
        min_num = min(count)   #每组的牌的个数最大应该到count中最小的那个数，所以遍历从2到min_num，其实这个区间就是牌组中元素个数的公约数，查找哪一个公约数合适
        for i in range(2,min_num+1):
            if all([ x%i == 0 for x in count]):   #all函数中是一个迭代类型，判断迭代的元素是否为真。在这里表示这个公约数是否能够使所有个数都对其求余为0，满足的话就返回True
                return True
        return False

C++

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int,int> Map;
        for (auto i : deck){
            Map[i]++;   #首先记录deck中元素出现的个数
        }
        int min_num = deck.size();
        for (auto c:Map){
            if (c.second < min_num){
                min_num = c.second;  #找到元素出现个数的最小值
            }
        for (int i =2;i<=min_num;i++){   #遍历从2到这个最小值
            int j = 0;
            for (auto c:Map){   #如果Map中元素出现的个数对i求余为0则j++，当j的个数和Map中元素个数相等的时候，表明i是Map中每个元素出现的公约数，那么直接返回ture
                if (c.second%i == 0){
                    j++;
                    
                }
            if (j == Map.size()){
                return true;
            }
            }
        }
        return false;   #如果遍历了2到元素出现的最小个数之间所有值，j都不等于deck.size(),表明没有公约数，则返回false
        }
    }
};