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

分析

看见插入和删除都要 $O(1)$ ，很自然想到利用可变长数组进行操作。但这样就引入了一个问题：变长数组中，获取单个元素通常都要求数组有序，且绝大部分时间复杂度都大于 $O(1)$ 。因此我们需要其他方法来实现。

注意到题目中并没有限制空间复杂度。因此我们可以通过引入哈希表，用哈希表记录数组下标。通过哈希表来判断元素是否存在，即可完美实现 $O(1)$ 的要求。删除操作中，由于直接删除会涉及到后续元素的前移，所以我们可以交换目标元素与数组最后一个元素的位置。从而在常数时间里移除元素。

解答

1
class RandomizedSet {
2
private:
3
  vector<int> nums;
4
  unordered_map<int, int> indices;
5
  mt19937 rng;
6
  uniform_int_distribution<int> dist;
7

8
public:
9
  RandomizedSet() {}
10

11
  bool insert(int val) {
12
    if (indices.count(val))
13
      return false;
14

15
    auto index = nums.size();
16
    nums.emplace_back(val);
17
    indices[val] = index;
18

19
    return true;
20
  }
21

22
  bool remove(int val) {
23
    if (!indices.count(val))
24
      return false;
25

26
    auto index = indices[val];
27
    auto last = nums.back();
28
    nums[index] = last;
29
    indices[last] = index;
30
    nums.pop_back();
31
    indices.erase(val);
32

33
    return true;
34
  }
35

36
  int getRandom() {
37
    uniform_int_distribution<int>::param_type parm(0, nums.size() - 1);
38

39
    return nums[dist(rng, parm)];
40
  }
41
};