面试经典150题 P380 O(1) 时间插入、删除和获取随机元素

---

时间轴

2025-10-04

init

---

题目：

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

https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

这题我本来以为 getRandom 只要概率相同即可，但是这个题检测时大概率设置了随机数种子，如果不是调用 rand()得出来的顺序必定和答案不同。
这题主要用 hashmap 存储 val,index，用 vector 做随机访问插入时直接放入 vector 的最后一位，删除时将被删除的元素与最后一个元素交换位置，然后弹出最后一个元素 pop_back(),要记得更改 hashmap 中因为交换而使得最后一个元素的 Index。

#include <algorithm>
#include <unordered_map>
#include <vector>

using std::unordered_map;
using std::vector;

class RandomizedSet {
private:
  unordered_map<int, int> umap;
  vector<int> vec;

public:
  RandomizedSet() {}

  bool insert(int val) {

    if (umap.count(val) == 0) {
      vec.push_back(val);
      umap[val] = vec.size() - 1;
      return true;
    } else {
      return false;
    }
  }

  bool remove(int val) {
    if (umap.count(val) == 0) {
      return false;
    } else {
      umap[vec.back()] = umap[val];
      std::swap(vec[umap[val]], vec.back());

      vec.pop_back();
      umap.erase(val);

      return true;
    }
  }

  int getRandom() { return vec[std::rand() % vec.size()]; }
};