題目描述:給定一個整數陣列 hand,代表一手牌,以及整數 groupSize。判斷是否能將所有牌分成若干組,每組恰好有 groupSize 張連續的牌。若可以則回傳 true,否則回傳 false。
解題思路:使用貪心策略。首先,若 hand.size() 不能被 groupSize 整除,則直接回傳 false,因為無法均分。
接下來使用有序的 map(std::map)統計每張牌的出現頻率。由於 map 按鍵值由小到大排列,每次從最小的牌開始嘗試組成一組 groupSize 張連續的牌。
具體做法:每次取 map 中最小的鍵(即最小的牌),嘗試從該牌開始,依序找 groupSize 張連續的牌(即 card, card+1, card+2, ..., card+groupSize-1)。每找到一張就將其計數減 1,若計數減為 0 則從 map 中刪除。若某張牌不存在(計數為 0),則無法組成連續群組,回傳 false。重複此過程直到 map 為空,表示所有牌都成功分組,回傳 true。
關鍵觀察:每次必須從最小的牌開始組牌,因為最小的牌只能作為某個群組的起點(沒有比它更小的牌可以包含它在中間或結尾的位置)。
時間複雜度:O(n log n) — 建立 map 需要 O(n log n);每張牌在 map 中最多被存取一次,而每次 map 操作為 O(log n),故總共為 O(n log n)。
空間複雜度:O(n) — map 最多儲存 n 個不同的鍵值對。
1. If hand.size() % groupSize != 0, return false.
2. Build an ordered map: count[card] = frequency for each card in hand.
3. While the map is not empty:
a. Let start = the smallest key in the map.
b. For i from 0 to groupSize - 1:
- If (start + i) is not in the map, return false.
- Decrement count[start + i] by 1.
- If count[start + i] == 0, remove it from the map.
4. Return true.排序 + 貪心 O(n log n):先將牌排序,然後用一個普通的 unordered_map 記錄頻率。依序遍歷排序後的牌,若該牌仍有剩餘,嘗試以它為起點組成連續群組。邏輯相同,但需要額外排序步驟。
優先隊列 O(n log n):使用最小堆來模擬有序 map 的行為,每次從堆頂取最小元素。概念上與有序 map 相同,但實作稍微不同;有序 map 更直覺且在此問題中更簡潔。
groupSize 張連續牌),應如何修改解法?