380. Insert Delete Get Random O(1)

Medium

Description

設計一個資料結構，支援 insert(val)、remove(val) 和 getRandom() 三個操作，每個操作的平均時間複雜度都是 O(1)。getRandom 回傳集合中的隨機元素，每個元素被選中的機率相同。

Example:

Input: [“RandomizedSet”,“insert”,“remove”,“insert”,“getRandom”,“remove”,“insert”,“getRandom”] > [[],[1],[2],[2],[],[1],[2],[]] Output: [null,true,false,true,2,true,false,2]

Intuition#

核心思路：結合 ArrayList 和 HashMap——ArrayList 支援 O(1) 隨機存取（getRandom），HashMap 支援 O(1) 查找與定位（insert/remove）。

HashMap 單獨無法 O(1) getRandom（無法隨機索引）
ArrayList 單獨無法 O(1) remove（需要搜尋）
結合兩者：HashMap 存 val -> index，ArrayList 存元素
刪除技巧：將要刪除的元素與最後一個元素交換，然後移除最後一個元素（O(1)）

Approaches#

1: HashMap + ArrayList (基本實作)#

概念: HashMap 記錄元素在 ArrayList 中的索引，刪除時用「swap with last」技巧
時間複雜度: 每個操作 O(1) 平均
空間複雜度: O(n) - 儲存 n 個元素

class RandomizedSet() {
    private val list = ArrayList<Int>()
    private val map = HashMap<Int, Int>()  // val -> index in list

    fun insert(`val`: Int): Boolean {
        if (`val` in map) return false
        map[`val`] = list.size
        list.add(`val`)
        return true
    }

    fun remove(`val`: Int): Boolean {
        val idx = map[`val`] ?: return false
        val lastVal = list[list.size - 1]

        // 將最後一個元素移到被刪除的位置
        list[idx] = lastVal
        map[lastVal] = idx

        // 移除最後一個元素
        list.removeAt(list.size - 1)
        map.remove(`val`)

        return true
    }

    fun getRandom(): Int {
        return list[(Math.random() * list.size).toInt()]
    }
}

⭐2: HashMap + ArrayList (使用 kotlin.random)#

概念: 同上結構，但使用 Kotlin 的 Random API 更乾淨
時間複雜度: 每個操作 O(1) 平均
空間複雜度: O(n) - 儲存 n 個元素

class RandomizedSet() {
    private val list = mutableListOf<Int>()
    private val indexMap = HashMap<Int, Int>()

    fun insert(`val`: Int): Boolean {
        if (`val` in indexMap) return false
        indexMap[`val`] = list.size
        list.add(`val`)
        return true
    }

    fun remove(`val`: Int): Boolean {
        val idx = indexMap[`val`] ?: return false
        val lastIdx = list.size - 1

        if (idx != lastIdx) {
            val lastVal = list[lastIdx]
            list[idx] = lastVal
            indexMap[lastVal] = idx
        }

        list.removeAt(lastIdx)
        indexMap.remove(`val`)
        return true
    }

    fun getRandom(): Int {
        return list.random()
    }
}

刪除時若要刪的就是最後一個元素（idx == lastIdx），不需要交換，直接移除即可。這個邊界情況容易被忽略，雖然不檢查也能正確運作（自己跟自己交換），但加上判斷更清晰。

🔑 Takeaways#

Pattern: O(1) insert + delete + getRandom -> ArrayList + HashMap 的經典組合
關鍵技巧: 「Swap with Last」刪除法——將待刪元素與陣列末尾交換再移除，保持連續性且 O(1)。這個技巧廣泛用於需要 O(1) 刪除的陣列場景