380. Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

題目描述：設計一個資料結構，支援三種操作，且每種操作的平均時間複雜度都必須是 O(1)：insert(val) — 插入元素（若已存在則忽略）；remove(val) — 刪除元素（若不存在則忽略）；getRandom() — 均勻隨機回傳集合中的任一元素。

解題思路：單純用 unordered_set 可以做到 O(1) 的插入與刪除，但無法在 O(1) 內取得隨機元素（需要迭代器隨機存取）。單純用 vector 可以 O(1) 取隨機元素，但刪除中間元素需要 O(n)。

關鍵洞察：將兩者結合。用一個 vector<int> 存放所有元素，用一個 unordered_map<int, int> 記錄每個元素在 vector 中的索引。

• insert：若元素不存在，直接 push_back 到 vector 末端，並在 map 中記錄其索引。
• remove：若元素存在，找到它在 vector 中的位置，將其與 最後一個元素交換，更新被移動元素的索引，然後 pop_back。這樣刪除操作只動末端，保持 O(1)。
• getRandom：用 rand() % size 隨機選取 vector 中的索引並回傳對應值。

「交換再刪末端」是這題最精妙的設計，讓 vector 的任意位置刪除變成 O(1)。

時間複雜度：O(1) 平均 — insert 和 remove 都是 unordered_map 與 vector 的常數時間操作；getRandom 直接用索引存取 vector，也是 O(1)。

空間複雜度：O(n) — 需要儲存 n 個元素的 vector 和同樣大小的 hash map，其中 n 為集合當前元素數量。

方法一：純 unordered_set（不可行） 使用 unordered_set 可以 O(1) 插入與刪除，但 getRandom 需要用迭代器走訪到第 k 個元素，時間為 O(n)，不符合要求。

方法二：有序 map + 跳表（可達到 O(log n)） 使用 std::map 或跳表可在 O(log n) 時間內完成三種操作，並透過 order statistics 實現 getRandom。優點是支援有序遍歷，但時間複雜度不如本題要求的 O(1)。

方法三：vector + unordered_map（本題最優解） 即上述主解法。insert 與 remove 皆為 O(1) 均攤，getRandom 為嚴格 O(1)。是此問題的標準最優解法，時間複雜度 O(1)，空間複雜度 O(n)。

1. 如果允許重複元素（每個值可以插入多次，刪除只移除一個實例），如何修改資料結構？（提示：indexMap 的值改為 unordered_set<int> 存放所有索引）
2. 如果 getRandom 需要根據每個元素插入的次數加權隨機（插入越多次被選中機率越高），設計應如何調整？
3. 在多執行緒環境下，如何確保 insert、remove、getRandom 的執行緒安全性，同時盡量保持高並行度？