Problem#
要你實作一個 class RandomizedSet() 有三個操作: 插入數字、移除數字、隨機取出數字，三種操作都必須在平均 $O(1)$ 時間複雜度下。
測資限制#
- $-2^{31} \le val \le 2^{31} - 1$
- 最多 $2\cdot 10^5$ 次呼叫
想法#
- naive: 插入跟刪除要 $O(1)$ 用
unordered_map可以很容易達到，但隨機存取也要 $O(1)$ 就無法只用 hashmap 了 - improve: 隨機存取還是要用
vector存連續的陣列，用來拿隨機的數字，至於插入和刪除，可以用一個 hashmap 來存數值 -> 出現在 vector 的 index，儲存 index 為了刪除時可以快速找到該數值在vector的位置- 插入: 直接將數值推入，並儲存數值對應的 index
- 刪除: 用數值找到 index 後，直接將陣列最後一個數字放到
vec[index](代表刪除)，記得 pop back 和儲存新 index (edge case: 陣列只剩下一個元素時) - 拿隨機: 直接拿
vector
AC Code#
- 時間複雜度: $\mathcal{O}(1)$
- 空間複雜度: $\mathcal{O}(n)$
心得#
意外的難想到隨機也能 $O(1)$ 的方法