题目

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]。

来源：力扣（LeetCode）

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

解答

先理解题意，无非就是给一组乱序的数组进行分组，每组数量一致并且每组都是顺子。

解题思路如下：

1. 进行数量判定，看是否能平均分成 groupSize 组，如果不能直接返回 false；
2. 构建哈希表，存储每一个数出现的次数；
3. 对数组 hand 进行排序，为什么需要排序？因为需要用到“贪心”的思想，即每次想要组成一个符合条件的顺子，一定有一个起始点，就是最小值。从当前数组中，选择最小的那个值，就一定是某个组内的最小值；
4. 以模拟方法，每次从 hand 中选取一个最小值，且该值没有被“使用”（使用就是已经被构成其他组的元素了）。然后根据 groupSize 依次从数组中查找是否有符合顺子的数（根据哈希表查询），如果有就继续循环，否则就返回 false。
5. 每次提取出合适的数字，记得将哈希表中的元素数量减 1 ，且取的时候，要注意是否可取。

具体代码如下：

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

        // 无法均分，则直接返回 false
        if (n % groupSize != 0) {
            return false;
        }

        // 组的数量
        int groupNums = n / groupSize;
        unordered_map<int, int> mp;
        for (auto i: hand) {
            mp[i]++;
        }

        sort(hand.begin(), hand.end());
        int count = 0;
        for (int i = 0; i < groupNums; ++i) {

            // 找到当前数组中最小的一个值，并从map中取出
            while (true) {
                if (mp[hand[count]] != 0) {
                    break;
                } else {
                    count++;
                }
            }
            int start = hand[count];
            mp[start]--;

            // 给找到的最小值，寻找它的顺子数
            for (int j = 0; j < groupSize - 1; ++j) {
                auto it = mp.find(start + j + 1);
                if (it == mp.end() || mp[it->first] == 0) {
                    return false;
                }
                
                mp[it->first]--;
            }
        }

        return true;
    }
};