插入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
热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短