給定一組整數牌
hand和一個整數groupSize，判斷能否將所有牌分成若干組，每組包含groupSize張連續的牌。
Example:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true ([1,2,3], [2,3,4], [6,7,8])
Intuition
TIP
從最小的牌開始，貪心地組成連續序列；若任何一張需要的牌不夠用，則不可能。
- 總牌數必須是 groupSize 的倍數，否則直接 false
- 排序後，從最小的牌開始嘗試組成連續序列
- 用 Map 記錄每張牌的剩餘數量
Approaches
1. Sort + HashMap — O(n log n) / O(n)
- Idea: 排序後遍歷，對每張牌嘗試作為新組的起點，依序消耗連續的牌。
- Time:
O(n log n)，排序主導 - Space:
O(n)
class Solution {
fun isNStraightHand(hand: IntArray, groupSize: Int): Boolean {
if (hand.size % groupSize != 0) return false
val count = TreeMap<Int, Int>()
for (card in hand) {
count[card] = (count[card] ?: 0) + 1
}
while (count.isNotEmpty()) {
val first = count.firstKey()
for (i in first until first + groupSize) {
val c = count[i] ?: return false
if (c == 1) {
count.remove(i)
} else {
count[i] = c - 1
}
}
}
return true
}
}⭐ 2. Sort + HashMap (optimized scan) — O(n log n) / O(n)
- Idea: 排序後用陣列遍歷，每次遇到尚有剩餘的牌就作為起點，減少 TreeMap 的常數開銷。
- Time:
O(n log n) - Space:
O(n)
class Solution {
fun isNStraightHand(hand: IntArray, groupSize: Int): Boolean {
if (hand.size % groupSize != 0) return false
hand.sort()
val count = HashMap<Int, Int>()
for (card in hand) {
count[card] = (count[card] ?: 0) + 1
}
for (card in hand) {
if ((count[card] ?: 0) == 0) continue
for (i in card until card + groupSize) {
val c = count[i] ?: return false
if (c == 0) return false
count[i] = c - 1
}
}
return true
}
}🔑 Takeaways
- Pattern: 貪心 + 排序 — 從最小元素開始逐步構建所需結構
- Key trick: TreeMap 的
firstKey()方便取最小值；這題和 LC 1296 (Divide Array in Sets of K Consecutive Numbers) 完全相同