846. Hand of Straights

Medium

Description

給定一組整數牌 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#

從最小的牌開始，貪心地組成連續序列；若任何一張需要的牌不夠用，則不可能。

總牌數必須是 groupSize 的倍數，否則直接 false
排序後，從最小的牌開始嘗試組成連續序列
用 Map 記錄每張牌的剩餘數量

Approaches#

1: 排序 + HashMap#

概念: 排序後遍歷，對每張牌嘗試作為新組的起點，依序消耗連續的牌。
時間複雜度: O(n log n)，排序主導
空間複雜度: 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: 排序 + HashMap（優化遍歷）#

概念: 排序後用陣列遍歷，每次遇到尚有剩餘的牌就作為起點，減少 TreeMap 的常數開銷。
時間複雜度: O(n log n)
空間複雜度: 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: 貪心 + 排序 — 從最小元素開始逐步構建所需結構
關鍵技巧: TreeMap 的 firstKey() 方便取最小值；這題和 LC 1296 (Divide Array in Sets of K Consecutive Numbers) 完全相同