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

1
输入
2
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
3
[[], [1], [2], [2], [], [1], [2], []]
4
输出
5
[null, true, false, true, 2, true, false, 2]
6

7
解释
8
RandomizedSet randomizedSet = new RandomizedSet();
9
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
10
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
11
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
12
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
13
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
14
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
15
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

1
class RandomizedSet {
2
public:
3
    RandomizedSet() {
4
        srand((unsigned)time(NULL));
5
    }
6

7
    bool insert(int val) {
8
        // val exists
9
        if(_indices.count(val)){
10
            return false;
11
        }
12
        // val not exist
13
        // get last index and add val
14
        int index = _nums.size();
15
        _nums.emplace_back(val);
16
        // record index
17
        _indices[val] = index;
18
        return true;
19
    }
20

21
    bool remove(int val) {
22
        // val not exist
23
        if(!_indices.count(val)){
24
            return false;
25
        }
26

27
        // get val index
28
        int index = _indices[val];
29
        int last = _nums.back();
30
        // move last val to replace current val
31
        _nums[index] = last;
32
        _indices[last] = index;
33
        // remove last val
34
        _nums.pop_back();
35
        _indices.erase(val);
36
        return true;
37
    }
38

39
    int getRandom() {
40
        int random_index = rand()%_nums.size();
41
        return _nums[random_index];
42
    }
43
private:
44
    vector<int> _nums;
45
    unordered_map<int, int> _indices;
46
};
47

48
/**
49
 * Your RandomizedSet object will be instantiated and called as such:
50
 * RandomizedSet* obj = new RandomizedSet();
51
 * bool param_1 = obj->insert(val);
52
 * bool param_2 = obj->remove(val);
53
 * int param_3 = obj->getRandom();
54
 */