题目地址: https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/
题目描述
Ina 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；
题目大意
判断一堆牌能不能分成很多组，每个组是相同的元素，并且每个组最少两张牌。
解题方法
遍历
果然是个Easy的题目，很简单。
每个组的元素都是相同的情况下，分组之后每个组有多少个元素呢？
首先，要求每个组的元素都是相同的，因此元素个数最小的那个组限制了每个组的个数。
但不一定是所有元素个数的最小值，因为相同的元素可以分成很多组的，比如这个测试用例，每个组可以都是两个元素即可。
[1,1,1,1,2,2,2,2,2,2]
所以，可以用一个遍历，从2遍历到最少次数的数字中的元素个数。道理是，把最少次数在划分和不划分的情况下，看其他组能不能按照这个个数进行均分。
最坏情况下的时间复杂度是O(N^2)，空间复杂度是O(N)。
Python代码如下：
class Solution(object):
def hasGroupsSizeX(self, deck):
"""
:type deck: List[int]
:rtype: bool
"""
count = collections.Counter(deck)
X = min(count.values())
for x in range(2, X + 1):
if all(v % x == 0 for v in count.values()):
return True
return False
1 2 3 4 5 6 7 8 9 10 11 12
最大公约数
二刷的时候想到了最大公约数解法。
最终分的组的大小是多少，就是每个数字的次数的最大公约数。
比如例子：
[1,1,2,2,2,2]
最终分成了[1,1],[2,2],[2,2]，每个组是2个数字，怎么得来的？看1出现了2次，看2出现了4次，最终的结果就是2和4的最大公约数2。
公约数能被所有的数字个数整除，所以最大的那个公约数，就是能被所有数字个数整除的最大组大小。
C++代码如下：
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> counter;
for (int d : deck) {
counter[d] ++;
}
int res = 0;
for (auto& c : counter) {
res = gcd(c.second, res);
}
return res > 1;
}
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发