LeetCode周赛#104 Q1 X of a Kind in a Deck of Cards (枚举)

题目来源：https://leetcode.com/contest/weekly-contest-104/problems/x-of-a-kind-in-a-deck-of-cards/

问题描述

914. X of a Kind in a Deck of Cards

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.

 

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

------------------------------------------------------------

题意

给定一个数列A，问数列A能不能分成n个部分（n>=1），每个部分元素个数>=2,且每个元素相同

------------------------------------------------------------

思路

用map记录数列A中每个元素出现的次数，问题转化为求这些次数的公因子。如果有大于等于2的公因子，则返回true。求公因子时采用枚举从2到最小数依次判断整除性的办法。

------------------------------------------------------------

代码

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        map<int, int> mp;
        map<int, int>::iterator it;
        int i, len = deck.size(), xmin = 0x3f3f3f3f, x;
        bool is_true = true;
        for (i=0; i<len; i++)
        {
            mp[deck[i]]++;
        }
        for (it=mp.begin(); it!=mp.end(); it++)
        {
            xmin = min(it->second, xmin);
        }
        for (x = 2; x <= xmin; x++)
        {
            is_true = true;
            for (it=mp.begin(); it!=mp.end(); it++)
            {
                if ((it->second)%x != 0)
                {
                    is_true = false;
                }
            }
            if (is_true)
            {
                return true;
            }
        }
        return false;
    }
};