插入 删除 获取随机数 O(1) - C++ 中允许重复
c++server side programmingprogramming更新于 2025/6/25 21:22:17
假设我们要创建一个数据结构，该结构支持某些操作，这些操作必须在 O(1) 的时间内完成。因此，让这些操作类似于 −
- insert(x):将 x 插入集合
- remove(x):从集合中删除 x
- getRandom():这将从该集合中查找随机元素。
为了解决这个问题，我们将遵循以下步骤 −
- 创建一个数组 nums
- 创建一个映射 m
- 定义一个函数 insert()，该函数接受 val
- 当 val 不在 m 中时，ret :=
- 在 m[val] 的末尾插入 nums 的大小
- insert { val, m[val] 的大小 – nums 末尾的 1} 对
- 返回 ret
- 定义一个函数 remove()，该函数接受 val
- 当 val 不在 m 中时，ret :=
- 如果 ret 非零，则减去
- last = nums 的最后一个元素
- m[last 的键][last 的值] := m[val] 的最后一个元素
- nums[[m[val]] 的最后一个元素 := last
- 从 m[val] 中删除最后一个元素
- 如果 m[val] 为空，则减去
- 从 m 中删除 val
- 从 nums 中删除最后一个元素
- 返回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
