文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

設計一個支持在平均 時間復雜度 O(1) 下， 執行以下操作的數據結構。

注意: 允許出現重復元素。

• insert(val)：向集合中插入元素 val。
• remove(val)：當 val 存在時，從集合中移除一個 val。
• getRandom：從現有集合中隨機獲取一個元素。每個元素被返回的概率應該與其在集合中的數量呈線性相關。

示例:

// 初始化一個空的集合。 RandomizedCollection collection = new RandomizedCollection();// 向集合中插入 1 。返回 true 表示集合不包含 1 。 collection.insert(1);// 向集合中插入另一個 1 。返回 false 表示集合包含 1 。集合現在包含 [1,1] 。 collection.insert(1);// 向集合中插入 2 ，返回 true 。集合現在包含 [1,1,2] 。 collection.insert(2);// getRandom 應當有 2/3 的概率返回 1 ，1/3 的概率返回 2 。 collection.getRandom();// 從集合中刪除 1 ，返回 true 。集合現在包含 [1,2] 。 collection.remove(1);// getRandom 應有相同概率返回 1 和 2 。 collection.getRandom();

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1-duplicates-allowed
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：LeetCode 380. 常數時間插入、刪除和獲取隨機元素（哈希+vector）

• 本題有重復數字，用一個哈希set存儲同一數字的所有下標

class RandomizedCollection {vector<int> arr;unordered_map<int, unordered_set<int>> m;//數字 - 對應的下標集合 public:/** Initialize your data structure here. */RandomizedCollection() {}/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */bool insert(int val) {bool flag = true;if(m.find(val) != m.end())//存在元素了flag = false;arr.push_back(val);//加入元素m[val].insert(arr.size()-1);//記錄位置return flag;}/** Removes a value from the collection. Returns true if the collection contained the specified element. */bool remove(int val) {if(m.find(val) == m.end())return false;int idx = *m[val].begin();//找到一個待刪元素的位置m[val].erase(m[val].begin());//刪除位置記錄if(m[val].empty())m.erase(val);int last = arr.back();//數組最后的元素，跟idx位置的元素交換m[last].insert(idx);//跟下一句順序不能變，如果是同一位置就會出錯m[last].erase(arr.size()-1); if(m[last].empty())m.erase(last);arr[idx] = last;//跟新idx位置的元素為 lastarr.pop_back();//last實際為要刪除的元素，pop刪除return true;}/** Get a random element from the collection. */int getRandom() {int idx = random() % arr.size();return arr[idx];} };

88 ms 26.5 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复（vector + 哈希）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。