题目

类型：设计
image.png

解题思路

对于 insert 和 remove 操作容易想到使用「哈希表」来实现 O(1) 复杂度
但对于 getRandom 操作，比较理想的情况是能够在一个数组内随机下标进行返回。

将两者结合，可以将哈希表设计为：以入参 val 为键，数组下标 loc 为值。

为了确保严格 O(1)，需要申请一个足够大的数组 nums（利用数据范围为 O(1) 时间插入、删除和获取随机元素 - 图2 ），并使用变量 idx 记录当前使用到哪一位（即下标在 [0, idx] 范围内均是存活值）。

对于几类操作逻辑：

  • insert 操作：使用哈希表判断 val 是否存在，存在的话返回 false，否则将其添加到 nums，更新 idx，同时更新哈希表；
  • remove 操作：使用哈希表判断 val 是否存在，不存在的话返回 false，否则从哈希表中将 val 删除，同时取出其所在 nums 的下标 loc，然后将 nums[idx] 赋值到 loc 位置，并更新 idx（含义为将原本处于 loc 位置的元素删除），同时更新原本位于 idx 位置的数在哈希表中的值为 loc（若 loc 与 idx 相等，说明删除的是最后一个元素，这一步可跳过）；
  • getRandom 操作：由于我们人为确保了 [0, idx] 均为存活值，因此直接在 [0, idx + 1) 范围内进行随机即可。

代码

  1. class RandomizedSet {
  2.     static int[] nums = new int[200010];
  3.     Random random = new Random();
  4.     Map<Integer, Integer> map = new HashMap<>();
  5.     int idx = -1;
  6.     public boolean insert(int val) {
  7.         if (map.containsKey(val)) return false;
  8.         nums[++idx] = val;
  9.         map.put(val, idx);
  10.         return true;
  11.     }
  12.     public boolean remove(int val) {
  13.         if (!map.containsKey(val)) return false;
  14.         int loc = map.remove(val);
  15.         if (loc != idx) map.put(nums[idx], loc);
  16.         nums[loc] = nums[idx--];
  17.         return true;
  18.     }
  19.     public int getRandom() {
  20.         return nums[random.nextInt(idx + 1)];
  21.     }
  22. }