846. 一手顺子

# 846. 一手顺子

难度：中等

# 题目：

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

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 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

# 分析

题目要求将数组 $\textit{hand}$ 中的牌分组使得每组的大小是 $groupSize$。假设数组 $hand$ 的长度是 $n$，只有当 $n\bmod\textit{groupSize}=0$ 时才可能完成分组，因此如果$n\mod\textit{groupSize}\ne0$ 则直接返回$\text{false}$。

当 $n \bmod \textit{groupSize} = 0$ 时，可以将数组 $\textit{hand}$ 中的牌分组使得每组的大小是 $\textit{groupSize}$，此时需要判断是否存在一种分组方式使得同一组的牌都是连续的。

由于每张牌都必须被分到某个组，因此可以使用贪心的策略。假设尚未分组的牌中，最小的数字是 xx，则如果存在符合要求的分组方式，xx 一定是某个组中的最小数字（否则 xx 不属于任何一个组，不符合每张牌都必须被分到某个组），该组的数字范围是 $[x, x + \textit{groupSize} - 1]$。在将 $x$ 到 $ x + \textit {groupSize} - 1$ 的 $\textit{groupSize}$ 张牌分成一个组之后，继续使用贪心的策略对剩下的牌分组，直到所有的牌分组结束或者无法完成分组。如果在分组过程中发现从最小数字开始的连续 $\textit{groupSize}$ 个数字中有不存在的数字，则无法完成分组。

首先对数组$\textit{hand}$ 排序，并使用哈希表记录数组 $\textit{hand}$ 中每个元素的出现次数，然后遍历数组 $\textit{hand}$，使用基于上述贪心策略的做法判断是否可以完成分组。贪心策略的具体做法如下：

将当前元素记为 xx，如果 xx 不在哈希表中则跳过，如果 xx 在哈希表中，则 xx 是某个组中的最小数字（因为数组 $\textit{hand}$ 有序，当遍历到 $x$ 时，$x$ 一定是所有尚未分组的元素中的最小数字），该组的数字范围是 $[x, x + \textit{groupSize} - 1]$；

如果可以完成分组，则 $x$ 到 $x + \textit{groupSize} - 1$ 的每个整数在哈希表中记录的出现次数都至少为 1，如果遇到某个整数的出现次数为 0 则无法完成分组，返回 $\text{false}$；

将 $x$ 到 $x + \textit{groupSize} - 1$ 的每个整数在哈希表中记录的出现次数减 1，如果出现次数减为 0 则从哈希表中移除该整数；

对于其余元素，重复上述操作，直到遍历结束。

遍历结束之后，如果没有出现无法完成分组的情况，返回 $\text{true}$。

# 代码

var isNStraightHand = function(hand, groupSize) {

    const n = hand.length;

    if (n % groupSize !== 0) {

        return false;

    }

    hand.sort((a, b) => a - b);

    const cnt = new Map();

    for (const x of hand) {

        cnt.set(x, (cnt.get(x) || 0) + 1);

    }

    for (const x of hand) {

        if (!cnt.has(x)) {

            continue;

        }

        for (let j = 0; j < groupSize; j++) {

            const num = x + j;

            if (!cnt.has(num)) {

                return false;

            }

            cnt.set(num, cnt.get(num) - 1);

            if (cnt.get(num) == 0) {

                cnt.delete(num);

            }

        }

    }

    return true;

};