題目要求設計一個插入、刪除、跟取隨機都要 O(1) 的類別 RandomizedSet。
先針對每個操作單純思考,用最直覺的資料型態個別解決單一一個操作看看。
經過上述的直覺思考,我們的 getRandom 跟 insert 大致上想法沒毛病,只需要一個存輸入值的 Array 跟一個以輸入值為 key 、 ???為 value 的 Map 就有可能實現。 那個 ??? 究竟該存什麼才能把 delete 也一起解決呢?
記憶當前 Array 的位置 (index),會這麼思考是因為如果我每次插入時,Array 新增一個輸入值,Map 也以輸入值為 key 、位置為 value,這樣的話 delete 時就能直接從 Map 抓到這個輸入值在 Array 中的位置,把它跟 Array 最後一個元素做調換再 pop 掉只需要 O(1),之後把 Map 更新位置資訊,刪除輸入值的 key,即可達成無痛刪除。
Leetcode
JavaScript