题目描述

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

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

样例

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

输入：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

算法

(multiset操作) $O(n \log n)$

1. 如果 W 不是 n 的因数，则直接返回 false。
2. 将数组插入到一个多重集合 (multiset) 中，然后对于每一组，首先取出集合中最小的数字，然后检查剩余的 W 个数字是否存在，若不存在，则返回 false。若存在，在集合中删掉该数字。
3. 检查过 n / W 组后，返回 true。

时间复杂度

• 一共需要判断 $O(n)$ 个数字，每次判断都需要 $O(\log n)$ 的时间，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外的多重集合，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        const int n = hand.size();

        if (n % groupSize != 0)
            return false;

        multiset<int> s(hand.begin(), hand.end());

        for (int i = 0; i < n / groupSize; i++) {
            int st = *s.begin();

            for (int j = st; j < st + groupSize; j++) {
                auto it = s.find(j);

                if (it == s.end())
                    return false;

                s.erase(it);
            }
        }

        return true;
    }
};