380. O(1) 时间插入、删除和获取随机元素(真随机数)

本文主要是介绍380. O(1) 时间插入、删除和获取随机元素(真随机数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

380. O(1) 时间插入、删除和获取随机元素
方案：
该题看似简单，但难点在于每个函数的时间复杂度均为o(1),
哈希表+动态数组
哈希表查找元素是否存在，时间复杂度O(1), 动态数组可以随机访问下标进行存取操作。
原答案：

#include <ctime>
#include <iostream>
#include <random>
#include <vector>
#include <map>using namespace std;
class RandomizedSet {
public:RandomizedSet() {std::srand(std::time(nullptr));}bool insert(int val) {map<int, int>::iterator ite= idxMap.find(val);if (ite != idxMap.end()) {return false;}myVec.push_back(val);idxMap[val] = myVec.size() - 1;return true;}bool remove(int val) {map<int, int>::iterator ite= idxMap.find(val);if (ite == idxMap.end()) {return false;}myVec[idxMap[val]] = myVec[myVec.size()-1];idxMap[myVec[myVec.size()-1]] = idxMap[val];myVec.pop_back();idxMap.erase(ite);return true;}int getRandom() {int idx = rand() % myVec.size();return myVec[idx];}
private:map<int, int> idxMap;vector<int> myVec;
};

这篇关于380. O(1) 时间插入、删除和获取随机元素(真随机数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---