[Java][LeetCode][Hash] 380. Insert Delete GetRandom O(1)

SP Hou
Jun 15, 2022

--

題目要求實作insert, remove, getRandom,開一個Map去紀錄值與位置,開一個List去紀錄掃過的值,並且之後要準備用List去做getRandom的隨機輸出。
insert: 加到Map與List中
remove: 從Map與List中移除該數值。移除前,要先將List中最後一個值放到將被移除的數值的位置,並且更新在Map的Key與Value。
getRandom: 以List的size隨機產生一個數,將此數輸出,這樣就可以達到the same probability

This problem requests to implement insert, remove, and get the random element. I am creating a Map to record value and index. Creating a List to record the value that was inserted.
insert: add value to map and list.
remove: remove value from map and list. Before removing the value, I need to get the last element of the list and replace the value that will be removed. Then remove the last element in the list and the Key of value in the Map.

--

--