实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1
背景
相关知识点：
①．vector 支持 O(1) 元素随机访问
②．vector 末尾删除元素是 O(1)
③．unordered_map 访问、添加、删除元素都是 O(1)
④．rand() 函数会返回一个从0到最大随机数的任意整数，可以通过 % 运算来限定范围
题目分析
题目要求 O(1) 时间读写元素，首先想到 set ，但是 set 不支持随机访问，因此考虑使用 vector ；由于 vector 除末尾位置外不支持 O(1) 的删除，本题的关键是把要删除的元素和末尾元素进行交换，然后可以以 O(1) 删除。
代码示例
class RandomizedSet {
private:
vector<int> m_vec;//用于数据的随机访问
unordered_map<int,int> m_map;//用于判断数据是否存在
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. */
bool insert(int val) {
if( m_map.find(val) != m_map.end() ) return false;//元素已经存在
m_vec.push_back(val);//插入元素
m_map[val] = m_vec.size()-1;//保存元素下标
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if( m_map.find(val) == m_map.end() ) return false;//元素不存在
int index = m_map[val];//获取元素位置
int temp = m_vec.back();//末尾元素值
m_vec[index] = temp;//把末尾元素值保存到当前元素的位置
m_map[temp] = index;//更新末尾元素值的下标
m_vec.pop_back();//删除末尾元素
m_map.erase(val);//删除元素位置
return true;
}
/** Get a random element from the set. */
int getRandom() {
if( m_vec.size() == 0 ) return -1;
int index = rand() % m_vec.size();//生成随机位置
return m_vec[index];
}
};
