原文链接: https://leetcode-cn.com/problems/hand-of-straights

英文原文

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards.

Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.

 

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

Example 2:

Input: hand = [1,2,3,4,5], groupSize = 4
Output: false
Explanation: Alice's hand can not be rearranged into groups of 4.

 

Constraints:

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

 

Note: This question is the same as 1296: https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

中文题目

爱丽丝有一手（hand）由整数数组给定的牌。 

现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。

如果她可以完成分组就返回 true，否则返回 false。

 

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= hand.length <= 10000
• 0 <= hand[i] <= 10^9
• 1 <= W <= hand.length

通过代码

官方题解

方法一：暴力解法【通过】

思路

因为手中最小的牌也一定是某个分组中的起始牌，所以反复从手中最小的牌开始组建一个长度为 W 的组。

算法

使用 TreeMap 或 dict 记录每种牌的数量 {card: number of copies of card}。

然后反复执行以下步骤：找到最小的一张牌（假设是 x），然后试图将 x, x+1, x+2, ..., x+W-1 这些牌的计数减 1。如果每次都能找到这样的组且最终手里无牌，那么分组成功，否则失败。

[solution1-Java]
class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        TreeMap<Integer, Integer> count = new TreeMap();
        for (int card: hand) {
            if (!count.containsKey(card))
                count.put(card, 1);
            else
                count.replace(card, count.get(card) + 1);
        }

        while (count.size() > 0) {
            int first = count.firstKey();
            for (int card = first; card < first + W; ++card) {
                if (!count.containsKey(card)) return false;
                int c = count.get(card);
                if (c == 1) count.remove(card);
                else count.replace(card, c - 1);
            }
        }

        return true;
    }
}

[solution1-Python]
class Solution(object):
    def isNStraightHand(self, hand, W):
        count = collections.Counter(hand)
        while count:
            m = min(count)
            for k in xrange(m, m+W):
                v = count[k]
                if not v: return False
                if v == 1:
                    del count[k]
                else:
                    count[k] = v - 1

        return True

复杂度分析

• 时间复杂度：$O(N * (N/W))$，其中 $N$ 是 hand 的长度，$(N / W)$ 是 min(count) 的复杂度。在 Java 中使用 TreeMap 可以将 $(N / W)$ 降低到 $\log N$。

• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
9213	17917	51.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言