常数时间对数组进行-删除-查找-随机提取元素

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

众所周知，数组这类数据结构可以实现O(1)的获取，所以结合rand()函数就能实现随机获取，但是数组的存储方式又是连续的，这就意味着，插入和删除时需要有大量的元素需要移动，所以不能实现O(1)的插入（末尾除外）和删除。能够实现O(1)的插入和删除的数据结构，有哈希表（可能还有其它，但是暂时没有学习到），通过哈希函数的映射能够实现O(1)的插入和删除，如此本题需要结合数组与哈希表。

插入由于题目意思应该是无需指定位置插入，所以直接插入在末尾处的话，可以直接push_back();

最终实现删除的方法：将要删除的元素替换到数组的末尾，所以需要哈希表来记录删除元素对应的下标。

bool remove(int val) {
        if (umap.find(val) != umap.end()) {
            int index = umap[val];
            umap[nums.back()] = index; // 这是我开始忽略的，实际上也是需要记录最后一个元素调换后的新下标。
            swap(nums[index], nums.back());
            nums.pop_back();
            umap.erase(val);
            return true;
        }
        return false;
    }

完整代码：

class RandomizedSet {
public:
    vector<int> nums;
    unordered_map<int, int> umap;
public:
    
    bool insert(int val) {
        if (umap.find(val) == umap.end()) {
            nums.push_back(val);
            umap[val] = nums.size() - 1;
            return true;
        }
        return false;
    }
    
    bool remove(int val) {
        if (umap.find(val) != umap.end()) {
            int index = umap[val];
            umap[nums.back()] = index;
            swap(nums[index], nums.back());
            nums.pop_back();
            umap.erase(val);
            return true;
        }
        return false;
    }
    
    int getRandom() {
        // 随机获取 nums 中的一个元素
        return nums[rand() % nums.size()];
    }
};