10 来，打一手“贪心”的牌

846. 一手顺子

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 10 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🟡中等

标签：#贪心数组哈希表排序

你手中有一把牌，你想要将它们分成若干组，使每组都有 groupSize 张，并且每组中的牌面数字是连续的（类似斗地主中的“顺子”）。

给你一个 int[] hand，其中 hand[i] 是第 i 张牌的牌面数字，判断你是否可以按要求分组。

输入: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
输出: true
解释: 牌可以分组为 [1,2,3],[2,3,4],[6,7,8]

解题思路

每组都必须有 groupSize 张，如果 len(hand) % groupSize > 0，直接返回 false。

考虑当前未分组的最小数字 x，由于每张牌都要分到某一组，x 一定会作为某个分组的最小数字。

确定了该组的最小数字，由于每组内的数字是连续的，该组的数字就全部确定了，即为 [x,...,x+groupSize-1]。

排序，对每种牌面数字计数（牌面取值 $[1, 1 0^{9}]$ ，需哈希表），然后每次选取当前未分组的最小数字，确定该分组的所有数字，将相应数字的计数减 1。

以用例 [1,2,3,6,2,3,4,7,8],3 为例：

排序：1,2,2,3,3,4,6,7,8。
计数：{1:1;2:2;3:2;4:1;6:1;7:1;8:1}。
分组：选最小数字 1，该分组确定为 1,2,3，对这 3 个数的计数减 1。
重复第 3 步，直到分组失败或完成所有分组。

复杂度

时间复杂度： $O (N lo g N)$
空间复杂度： $O (N)$

代码

Java

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if (hand.length % groupSize > 0) return false;
        Map<Integer, Integer> count = new HashMap<>();
        for (int card : hand) count.merge(card, 1, Integer::sum);
		
        Arrays.sort(hand);
        for (int card : hand) {
            if (count.get(card) == 0) continue;
            int curSize = 0;
            while (curSize < groupSize && count.getOrDefault(card, 0) > 0) {
                count.merge(card, -1, Integer::sum);
                card++;
                curSize++;
            }
            if (curSize != groupSize) return false;
        }
		
        return true;
    }
}

Python

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize > 0:
            return False
        count = Counter(hand)
        
        hand.sort()
        for card in hand:
            if count[card] == 0:
                continue
            curSize = 0
            while curSize < groupSize and count.get(card, 0) > 0:
                count[card] -= 1
                card += 1
                curSize += 1
            if curSize != groupSize:
                return False
        
        return True

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer