題目網址：https://leetcode.cn/problems/hand-of-straights/

題意：Alice 手中有一堆牌, 她想要重新排列這些牌, 將其分成若干組, 使每一組的牌數都是 groupSize, 並且由 groupSize 張連續的牌組成。

給一整數 array hand 和一整數 groupSize, 其中 hand[i] 代表第 i 張牌。如果她可以重新排列這些牌, 返回 true；否則, 返回 false。

Solution：

想法：利用 Greedy, 首先判斷 hand.size() 能否被 groupSize 所整除, 若不行則返回 false。否則, 用 map 統計每張牌出現的次數, 並且根據 card value 由小到大排序。每個 group 每次都先從 map 中取出最小的 card value start, 則該 group 的數字範圍為 [start, start + groupSize - 1], 只要缺少一個便直接返回 false

取出數字後, 要將其出現次數減一, 然後判斷是否為 0。若是的話, 要將其移除, 否則 start 會一直取到同一個數

e.g. freqs = {{1, 1}, {2, 1}}, groupSize = 1

  • 若不移除 cnt = 0 的元素, 則取完第一個 group 後, freqs = {{1, 0}, {2, 1}}
  • 第二個 group 的 start 仍會取到 1, 而非 2
class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }

        map<int, int> freqs; // {card value, cnt}
        for (const auto& card : hand) {
            ++freqs[card];
        }

        while (!freqs.empty()) {
            const int start = freqs.begin()->first; // group 開頭數字

            // group range : [start, start + groupSize - 1]
            for (int i = 0; i < groupSize; ++i) {
                if (freqs[start + i] == 0) { // 該 group 內有數字不存在
                    return false;
                }

                // 取出該數字, 並將其出現次數減一, 然後判斷是否為 0
                // 若是的話, 要將其移除, 否則 start 會一直取到同一個數
                if (--freqs[start + i] == 0) {
                    freqs.erase(start + i);
                }
            }
        }

        return true;
    }
};
  • time：$O(n \cdot log(n))$ ➔ map 移除元素需花 $O(log(n))$, worse case：每個 hand[i] 都是 unique
  • space：$O(n)$ ➔ freqs