Hard

381. Insert Delete GetRandom O(1) - Duplicates allowed

arrayhash-tablemathdesignrandomized

解題說明

Insert Delete GetRandom O(1) - Duplicates allowed

題目描述：設計一個支援重複元素的資料結構，要求 insert、remove 和 getRandom 三個操作均為平均 O(1) 時間。getRandom 應根據元素出現的頻率等機率回傳。

解題思路：延續 LeetCode 380 的思路，使用一個動態陣列 vals 存放所有元素，一個雜湊表 indices 將每個值映射到它在 vals 中所有索引的集合（unordered_set）。插入時，直接在 vals 末端加入元素並更新索引集合。刪除時，將待刪元素與 vals 末端元素交換，再移除末端。交換時需同步更新兩個元素在 indices 中的索引資訊。getRandom 直接對 vals 隨機取索引即可。

C++ 解法

複雜度分析

時間複雜度：insert O(1)、remove O(1)、getRandom O(1) — 均為攤銷常數時間。

空間複雜度：O(n) — 其中 n 為所有已插入元素的總數（含重複）。

虛擬碼

1. Data: array vals[], hash map indices: val -> set of indices
2. Insert(val):
   a. notPresent = (val not in indices)
   b. Add vals.size() to indices[val]
   c. Append val to vals
   d. Return notPresent
3. Remove(val):
   a. If val not in indices, return false
   b. removeIdx = any index from indices[val]
   c. lastVal = vals.back()
   d. Overwrite vals[removeIdx] = lastVal
   e. Update indices: remove removeIdx from val's set, add removeIdx to lastVal's set, remove last index from lastVal's set
   f. Pop vals.back()
   g. If indices[val] is empty, erase key
   h. Return true
4. GetRandom(): return vals[random index in [0, vals.size())]

其他解法

使用 std::set 替代 unordered_set：將索引集合改為有序集合。操作變為 O(log n)，但在刪除時可以確定性地取最小/最大索引，避免 unordered_set 的雜湊碰撞問題。

鏈結串列 + 雜湊表：每個值維護一個雙向鏈結串列節點列表，雜湊表映射值到鏈結串列頭。插入刪除均為 O(1)，但 getRandom 無法 O(1)，需要額外的陣列來支援隨機存取。

延伸思考

如何讓 getRandom 使用更均勻的隨機數產生器（如 C++ 的 mt19937）？
若需要支援 getRandomDistinct()（每個值只算一次），該如何設計？
在多線程環境下，如何使這個資料結構線程安全？

Insert Delete GetRandom O(1) - Duplicates allowed — CaffeCode