846. 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

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

        // 使用 TreeMap 計算每個數字的頻率
        // TreeMap 裡面的 key 會從小到大排列
        map<int, int> freq;
        for(auto h : hand) ++freq[h];

        while(!freq.empty()) {
            // TreeMap 的第一個數字，也就是陣列裡最小的數字
            int first = freq.begin()->first;

            // 從 first 當作起始點，遞增到 < first + groupSize
            // 也就是遞增到每個 group 的最大值
            for(int i = first; i < first + groupSize; ++i){

                // 如果 i 不存在 freq 裡的話，代表這個數字已經被其他 group 用完了
                if(!freq.count(i)) {
                    return false;
                }

                // 如果 i 存在在 freq 裡的話，頻率減一
                --freq[i];

                // 頻率扣到為 0 的話，刪除這個 key
                if(freq[i] == 0) {
                    freq.erase(i);
                }
            }
        }
        return true;
    }
};

• T: $O(n \cdot \log n)$
• S: $O(n)$