插入Delete GetRandom O(1)-C ++中允许重复

假设我们要创建一个支持某些操作的数据结构，这些操作必须在O(1)的时间内执行。所以让这些操作像-

• insert(x)：将x插入集合

• remove(x)：从集合中删除x

• getRandom()：这将找到该集合的随机元素形式。

为了解决这个问题，我们将遵循以下步骤-

• 制作一个数组

• 制作一张映射

• 定义一个函数insert()，将需要val，

• ret：=当val不在m中时

• 在m [val]的末尾插入nums的大小

• 在数字末尾插入{val，m [val] – 1}的大小对

• 返回ret

• 定义一个函数remove()，将需要val，

• ret：=当val不在m中时

• 如果ret不为零，则-

• 从m删除val

• last = nums的最后一个元素

• m [last键] [last值]：= m [val]的最后一个元素

• nums [[m [val]]的最后一个元素：=最后一个

• 从m [val]删除最后一个元素

• 如果m [val]为空，则-

• 从num中删除最后一个元素

• 返回ret

• 定义功能 getRandom()

• 从集合中返回一个随机元素

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class RandomizedCollection {
public:
   vector <pair <int, int>> nums;
   unordered_map <int, vector<int>> m;
   RandomizedCollection() {
   }
   bool insert(int val) {
      bool ret = m.find(val) == m.end();
      m[val].push_back(nums.size());
      nums.push_back({val, m[val].size() - 1});
      return ret;
   }
   bool remove(int val) {
      bool ret = m.find(val) != m.end();
      if(ret){
         pair <int, int> last = nums.back();
         m[last.first][last.second] = m[val].back();
         nums[m[val].back()] = last;
         m[val].pop_back();
         if(m[val].empty())m.erase(val);
         nums.pop_back();
      }
      return ret;
   }
   int getRandom() {
      return nums[rand() % nums.size()].first;
   }
};
main(){
   RandomizedCollection ob;
   ob.insert(10);
   ob.insert(35);
   ob.insert(20);
   ob.insert(40);
   cout << (ob.getRandom()) << endl;
   ob.remove(20);
   cout << (ob.getRandom()) << endl;
}

输入值

Insert 10, 35, 20, 40, then get one random number, say 40, then remove 20, again get random element, that is say 35.

输出结果

40
35