Description
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 <= deck.length <= 10000
0 <= deck[i] < 10000
Solutions
1. Hash Table
本来想着直接存一个字典,看下 value 值是否都一样就可以了,后来发现,这个 group 里的值也可以和其他的 group 里的值一样,于是参考得到一个解决办法是,只要所有 value 值的最大公约数是大于 1 的,就说明多的那些可以拆成大小一致的 group!
from functools import reduce
# Time: O(n)
# Space: O(n)
class Solution:
def hasGroupsSizeX1(self, deck: List[int]) -> bool:
def gcd(a, b):
while b:
a, b = b, a % b
return a
count = collections.Counter(deck).values()
return reduce(gcd, count) > 1
def hasGroupsSizeX(self, deck: List[int]) -> bool:
count = collections.Counter(deck).values()
res = 0
for cnt in count:
res = self.gcd(cnt, res)
return res > 1
def gcd(self, a, b):
while b:
a, b = b, a % b
return a
# 74/74 cases passed (144 ms)
# Your runtime beats 56.29 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)
2. Array
先给 nums 排序,接着两层遍历:
- 让 i 从 2 开始往后面遍历,把 i 当做每个 group 的大小
- 在每一次遍历中,再从 0 开始检查没 i 个连续子数组转成 set 后大小是否为 1,是就返回真
# Time: O(n^2)
# Space: O(n)
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
n = len(deck)
deck.sort()
for i in range(2, n+1):
if n % i == 0:
flag = True
j = 0
while j < n:
if len(set(deck[j:j+i])) != 1:
flag = False
j += i
if flag:
return True
return False
# 69/69 cases passed (164 ms)
# Your runtime beats 14.11 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.7 MB)