事情会改变，朋友会离去。生命不会为了任何人而停歇。

题目描述：

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。

解题代码：

class RandomizedSet {
public:
    unordered_map<int, int> data;

    RandomizedSet() {

        data.clear();

    }
    
    bool insert(int val) {
        if (data.find(val) != data.end()) {
            return false;
        }
        data[val] = data.size();
        return true;
    }
    
    bool remove(int val) {
        if (data.find(val) == data.end()) {
            return false;
        }
        data.erase(val);
        return true;
    }
    
    int getRandom() {
        int n = data.size();
        int index = rand() % n;
        int i = 0;
        for (auto it = data.begin(); it != data.end(); it++) {
            if (i == index) {
                return it->first;
            }
            i++;
    }
    return -999;
    }
};

总结收获：

题目要求在o(1)复杂度内实现集合的增，删，和随机获取，o（1）复杂的首选哈希表，在题目给的类中加入新的元素：哈希表data，用来存放数据，之后再调用哈希表本身自带的方法即可实现o(1)复杂度增删，但取随机元素会比较复杂，最坏情况需要o（n）的复杂度，因此这并不是最优解。

优化：

class RandomizedSet {
public:

    vector<int> nums;
    unordered_map<int, int> data;

    RandomizedSet() {

        srand((unsigned)time(NULL));

    }
    
    bool insert(int val) {
        if (data.count(val) != 0) {
            return false;
        }
        data[val] = data.size();
        nums.emplace_back(val);
        return true;
    }
    
    bool remove(int val) {
        if (data.count(val) == 0) {
            return false;
        }
        int index = data[val];
        int last = nums.back();
        nums[index] = last;
        data[last] = index;
        nums.pop_back();
        data.erase(val);
        return true;
    }
    
    int getRandom() {
        int index = rand() % nums.size();
        return nums[index];
    }
};