Eric 的小站

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

5
    bool insert(int val) {
6
        if (map.find(val) != map.end())
7
            return false;
8
        values.push_back(val);
9
        map.insert(pair<int, int>(val, (int)values.size() - 1));
10
        return true;
11
    }
12

13
    bool remove(int val) {
14
        if (map.find(val) == map.end())
15
            return false;
16
        int last_index = values.back();
17
        int index = map[val];
18
        values[index] = last_index;
19
        map[last_index] = index;
20
        values.pop_back();
21
        map.erase(val);
22
        return true;
23
    }
24

25
    int getRandom() {
26
        int random = std::rand() % (values.size());
27
        return values[random];
28
    }
29

30
private:
31
    std::vector<int> values;
32
    std::unordered_map<int, int> map;
33
};

1
RandomizedSet() {
2
    srand((unsigned)time(NULL));
3
}