LeetCode刷题实战380：O(1) 时间插入、删除和获取随机元素
示例
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
解题
class RandomizedSet {
private:
unordered_map<int,int> hash;//哈希实现删除
vector<int> v;//动态数组实现插入和随机访问
public:
/** Initialize your data structure here. */
RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
//当元素 val 不存在时，向集合中插入该项。
bool insert(int val) {
if(hash.find(val) != hash.end()) return false; //如果集合中已经存在val，返回false，
v.push_back(val);//否则插入到数组末尾
hash[val] = v.size() - 1;//
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
//元素 val 存在时，从集合中移除该项。
bool remove(int val) {
if(hash.find(val) == hash.end()) return false;//如果集合中不存在val，返回false
int lastPos = v.size() - 1;//数组最后一个元素位置
int valPos = hash[val];//将被删除值和数组最后一位进行交换
v[valPos] = v[lastPos];
v.pop_back();//删除
hash[v[valPos]] = valPos;//被交换的值下标发生变化，需要更新
hash.erase(val); //哈希表中删除val的项
return true;
}
/** Get a random element from the set. */
//随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
int getRandom() {
int size = v.size();
int pos = rand() % size;//对下标产生随机数
return v[pos];//数组可以根据下表返回
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/