0846. 一手顺子【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 哈希表
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

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 <= 10^4
• 0 <= hand[i] <= 10^9
• 1 <= groupSize <= hand.length

---

注意：此题目与 1296. 划分数组为连续数字的集合 重复：

2. 🎯 s.1 - 贪心 + 哈希表

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

bool isNStraightHand(int* hand, int handSize, int groupSize) {
    if (handSize % groupSize != 0) return false;
    qsort(hand, handSize, sizeof(int), cmp);
    int* vals = (int*)malloc(sizeof(int) * handSize);
    int* cnts = (int*)malloc(sizeof(int) * handSize);
    int m = 0;
    for (int i = 0; i < handSize; i++) {
        if (m > 0 && vals[m-1] == hand[i]) cnts[m-1]++;
        else { vals[m] = hand[i]; cnts[m] = 1; m++; }
    }
    for (int i = 0; i < m; i++) {
        if (cnts[i] == 0) continue;
        int c = cnts[i];
        for (int j = 0; j < groupSize; j++) {
            if (i + j >= m || vals[i+j] != vals[i] + j || cnts[i+j] < c) {
                free(vals); free(cnts); return false;
            }
            cnts[i+j] -= c;
        }
    }
    free(vals); free(cnts);
    return true;
}

js

/**
 * @param {number[]} hand
 * @param {number} groupSize
 * @return {boolean}
 */
var isNStraightHand = function (hand, groupSize) {
  if (hand.length % groupSize !== 0) return false
  hand.sort((a, b) => a - b)
  const map = new Map()
  for (const c of hand) map.set(c, (map.get(c) || 0) + 1)
  for (const c of hand) {
    if (map.get(c) === 0) continue
    for (let i = 0; i < groupSize; i++) {
      if ((map.get(c + i) || 0) === 0) return false
      map.set(c + i, map.get(c + i) - 1)
    }
  }
  return true
}

py

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0: return False
        from collections import Counter
        cnt = Counter(hand)
        for card in sorted(cnt):
            c = cnt[card]
            if c == 0: continue
            for i in range(groupSize):
                if cnt[card + i] < c: return False
                cnt[card + i] -= c
        return True

• 时间复杂度：$O(n\log n)$，其中 n 是牌数
• 空间复杂度：$O(n)$

算法思路：

• 排序后统计每张牌的数量，贪心地从最小牌开始组顺子
• 每次将当前牌的计数消耗到后续 groupSize-1 张连续牌中

3. 🔗 引用

• 1296. 划分数组为连续数字的集合