数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中插入、删除和获取随机数 O(1) - 允许重复
假设，我们想要创建一个支持某些操作的数据结构，这些操作必须在 O(1) 的时间内完成。所以这些操作例如：
- insert(x)：将 x 插入集合
- remove(x)：从集合中删除 x
- getRandom()：这将从集合中找到随机元素。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个数组 nums
- 创建一个映射 m
- 定义一个函数 insert()，它将接收 val，
- ret := 当 val 不在 m 中时
- 在 m[val] 的末尾插入 nums 的大小
- 在 nums 的末尾插入 {val, m[val] 的大小 - 1} 对
- 返回 ret
- 定义一个函数 remove()，它将接收 val，
- ret := 当 val 不在 m 中时
- 如果 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
更新于: 2020-06-01
101 次浏览
广告