Medium

题目描述

Alice 有一些数字卡片，她想把这些卡片重新排列成若干组，使得每一组的大小都是 groupSize，且每一组都由 groupSize 张连续的卡片组成。

给你一个整数数组 hand，其中 hand[i] 是写在第 i 张卡片上的数值。还有一个整数 groupSize，请你判断 Alice 是否能够重新排列这些卡片，如果能，返回 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 题相同：https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

解题思路

这是一道贪心算法题目。要想把数组分成若干个大小为 groupSize 的连续子序列，我们需要满足以下条件：

  1. 数组长度能被 groupSize 整除：这是必要条件，否则无法分组
  2. 每个数字出现次数满足分组需求：对于最小的数字，它必须作为某些组的起始元素

核心思路： 使用贪心策略，总是从最小的未使用数字开始构建连续序列。具体步骤：

  1. 统计每个数字的出现次数
  2. 将数字按从小到大排序
  3. 对于每个数字，如果它还有剩余：
    • 尝试以它为起点构建一个长度为 groupSize 的连续序列
    • 检查后续 groupSize-1 个连续数字是否都有足够的剩余次数
    • 如果可以构建，则将这些数字的计数都减1
    • 如果不能构建完整序列，返回 false

为什么贪心策略正确？ 对于当前最小的数字，它只能作为某个组的第一个元素（因为它前面没有更小的数字可以和它连续）。所以我们必须用它来开始构建序列，这就是贪心选择的正确性。

时间复杂度主要来自排序操作，整体算法高效且易于理解。

代码实现

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) return false;
        
        map<int, int> count;
        for (int card : hand) {
            count[card]++;
        }
        
        while (!count.empty()) {
            int start = count.begin()->first;
            for (int i = 0; i < groupSize; i++) {
                if (count[start + i] == 0) return false;
                count[start + i]--;
                if (count[start + i] == 0) {
                    count.erase(start + i);
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        if len(hand) % groupSize != 0:
            return False
        
        from collections import Counter
        count = Counter(hand)
        
        while count:
            start = min(count)
            for i in range(groupSize):
                if count[start + i] == 0:
                    return False
                count[start + i] -= 1
                if count[start + i] == 0:
                    del count[start + i]
        
        return True

public class Solution {
    public bool IsNStraightHand(int[] hand, int groupSize) {
        if (hand.Length % groupSize != 0) return false;
        
        var count = new SortedDictionary<int, int>();
        foreach (int card in hand) {
            count[card] = count.GetValueOrDefault(card, 0) + 1;
        }
        
        while (count.Count > 0) {
            int start = count.Keys.First();
            for (int i = 0; i < groupSize; i++) {
                if (!count.ContainsKey(start + i) || count[start + i] == 0) {
                    return false;
                }
                count[start + i]--;
                if (count[start + i] == 0) {
                    count.Remove(start + i);
                }
            }
        }
        
        return true;
    }
}

var isNStraightHand = function(hand, groupSize) {
    if (hand.length % groupSize !== 0) return false;
    
    const count = new Map();
    for (const card of hand) {
        count.set(card, (count.get(card) || 0) + 1);
    }
    
    const sortedKeys = Array.from(count.keys()).sort((a, b) => a - b);
    
    for (const start of sortedKeys) {
        if (count.get(start) > 0) {
            const needed = count.get(start);
            for (let i = 0; i < groupSize; i++) {
                const current = start + i;
                if (!count.has(current) || count.get(current) < needed) {
                    return false;
                }
                count.set(current, count.get(current) - needed);
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n log n)，其中 n 是数组长度。主要消耗在排序或维护有序结构上
空间复杂度O(n)，用于存储数字出现次数的哈希表