一手顺子

标签: 贪心 数组 哈希表 排序

难度: Medium

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌上的数值。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

示例 1：

输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出：true
解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

示例 2：

输入：hand = [1,2,3,4,5], groupSize = 4
输出：false
解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。

提示：

  • 1 <= hand.length <= 104
  • 0 <= hand[i] <= 109
  • 1 <= groupSize <= hand.length

注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Submission

运行时间: 59 ms

内存: 17.3 MB

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if groupSize == 1:
            return True
        if len(hand) % groupSize != 0:
            return False


        cnts = Counter(hand)
        for start in sorted(cnts.keys()):
            c = cnts[start]
            if c <= 0:
                continue
                
            for end in range(start, start + groupSize):
                if cnts[end] < c:
                    return False
                cnts[end] -= c
        return True

Explain

首先，检查是否可以将手中的牌分成等大小的组，即手中的牌的数量必须是 groupSize 的整数倍。接下来，使用一个计数器 cnts 来统计每张牌出现的次数。然后，对计数器的键（也就是牌的数值）进行排序，依次检查每个数值作为起点的 groupSize 张连续牌是否存在且数量足够。如果存在连续的 groupSize 张牌，则从计数器中减去相应的数量，表示这些牌已经被使用。最后，如果所有的牌都能按要求分组，则返回 true，否则返回 false。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if groupSize == 1:
            return True
        if len(hand) % groupSize != 0:
            return False

        cnts = Counter(hand)
        for start in sorted(cnts.keys()):
            c = cnts[start]
            if c <= 0:
                continue

            for end in range(start, start + groupSize):
                if cnts[end] < c:
                    return False
                cnts[end] -= c
        return True

Explore

检查`len(hand) % groupSize != 0`是为了确保手中的牌能够被完全分成大小为`groupSize`的组。如果这个条件失败，即`len(hand)`不能被`groupSize`整除，这意味着牌的总数不能均匀分配成所需的组大小，因此无法形成所需的顺子组，直接返回`false`是为了提前结束程序，避免无谓的计算。

当`cnts[start]`的计数为零时，表示这张牌已经被完全用于之前的组合或者本来就不存在这张牌。因此，没有必要再考虑以这张牌作为新组的起始牌，可以直接跳过，以提高算法的效率。

在Python中，使用`Counter`对象时，尝试访问`Counter`中不存在的键将返回0，而不是引发错误。因此，在这种情况下直接检查`cnts[end] < c`既可以判断牌的数量是否足够，也能处理牌不存在的情况。这样做简化了代码，避免了不必要的键存在性检查。

如果`groupSize`大于手中牌的种类数量，算法仍然可以正确执行，但结果会是`false`。因为在这种情况下，无法找到足够的连续数值来形成一个有效的组。算法会在尝试构建第一个组时因找不到足够的连续牌而失败，从而返回`false`。