🔗 🟡 846. Hand of Straights 1565

tags: `Weekly Contest 87` `貪心(Greedy)` `雜湊表(Hash Table)` `排序(Sorting)`

題意

給定一個長度為 $n$ 的陣列 $hand$ ，其中 $hand[i]$ 代表第 $i$ 張牌上的數值，以及一個整數 $groupSize$ ，如果可以將這些牌重新排列成若干組，使每組的大小為 $groupSize$ ，而且每組包含 $groupSize$ 張連續的牌，則返回 $\rm{True}$ ，否則返回 $\rm{False}$ 。

約束條件

$1 \leq n \leq 10^4$
$0 \leq hand[i] \leq 10^9$
$1 \leq groupSize \leq n$

思路：貪心(Greedy) + 雜湊表(Hash Table) + 排序(Sorting)

基於貪心思路，由於我們需要組成連續的牌，因此手牌中最小的牌必會是一組連續牌的起點。假設手牌中最小的牌為 $x$ ，則我們需要組成 $x, x+1, x+2, ..., x+groupSize-1$ 這 $groupSize$ 張牌。

因此我們可以使用一個雜湊表(Hash Table) $cnt$ 來記錄每張牌的數量，並且對其鍵值進行排序（或是使用 C++ 的 map）來確保我們能夠從最小的牌開始檢查連續性。

具體步驟如下：

使用 Counter 或 map 來統計每張牌的數量，並依照鍵值排序。
遍歷排序後的鍵值，對每張牌進行檢查，如果該牌的數量為 $0$ ，則跳過。否則則嘗試組成以這張牌為起點的連續組合，共需要組成 $cnt[k]$ 組連續牌的集合。
如果某張牌無法組成連續組合（即該組內的某張牌的剩餘數量小於需要的數量），則返回 $\rm{False}$ 。
每次成功組成一個連續組合後，減少相應牌的數量。
如果所有牌都能成功組成連續組合，則返回 $\rm{True}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$
- 統計每張牌的數量需要 $\mathcal{O}(n)$ 時間。
- 排序需要 $\mathcal{O}(m \log m)$ 時間，其中 $m$ 為不同的牌的個數，可以視為 $\mathcal{O}(n)$ 。
- 每張牌最多會被遍歷一次，因此處理所有牌的過程需要 $\mathcal{O}(m + n)$ 時間，可以視為 $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ ，忽略排序的空間複雜度。

class Solution:
    def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
        cnt = Counter(hand)
        for k in sorted(cnt.keys()):
            if cnt[k] == 0:
                continue
            need = cnt[k]
            for i in range(groupSize):
                if cnt[k+i] < need:
                    return False
                cnt[k+i] -= need
        return True

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        map<int, int> cnt; // ordered map
        for (int x : hand) cnt[x]++;
        for (auto it = cnt.begin(); it != cnt.end(); it++) {
            if (it->second == 0) continue;
            int need = it->second;
            for (int i = 0; i < groupSize; i++) {
                if (cnt[it->first + i] < need) return false;
                cnt[it->first + i] -= need;
            }
        }
        return true;
    }
};