题目描述

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有相同的概率被返回。
你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1

思路

要求常数时间内完成插入删除操作显然可以使用 map.
如果要求在O(1)内完成数据的随机访问,得用vector这类容器.

如果使用vector存储数据的话,显然可以完成常数时间内插入和随机访问的任务,但是删除指定元素呢?

对于顺序表而言,删除数据后会花费大量时间在整理空间上面,如果要删除的每个元素都在末尾那么就可以避免这个问题了.

由此可以得出,可以尝试用map存储val与index的对应关系,当需要删除元素的时候,先将元素与末尾元素进行位置调整,再进行删除.

class RandomizedSet {
public:
    unordered_map<int,int> hash;
    vector<int>nums;
   
    RandomizedSet() {

    }
    
    bool insert(int val) {
		if(hash.count(x)==0){
            nums.push_back(x);
            hash[x]=nums.size()-1;
            return true;
        }
    }
    
    bool remove(int val) {
		if(hash.count(x)){
            int y = nums.back();
            int px = hash[x],py=hash[y];
            swap(nums[px],nums[py]);
            swap(hash[x],hash[y]);//交换vector值之后千万不要忘记交换hash值
            nums.pop_back();
            hash.erase(x);
            return true;
        }
    }
    
    int getRandom() {
		return nums[rand()% nums.size()]//直接使用rand()(伪随机)
    }
};