0380. O(1) 时间插入、删除和获取随机元素【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表 + 动态数组

1. 📝 题目描述

• leetcode

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1)。

示例：

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

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

---

提示：

• -2^31 <= val <= 2^31 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

2. 🎯 s.1 - 哈希表 + 动态数组

c

#define CAP 100001

typedef struct {
    int* list;
    int size;
    int map[CAP * 2 + 1]; // offset for negative keys
    bool has[CAP * 2 + 1];
} RandomizedSet;

RandomizedSet* randomizedSetCreate() {
    RandomizedSet* obj = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    obj->list = (int*)malloc(sizeof(int) * CAP);
    obj->size = 0;
    memset(obj->has, false, sizeof(obj->has));
    return obj;
}

bool randomizedSetInsert(RandomizedSet* obj, int val) {
    int key = val + CAP;
    if (obj->has[key]) return false;
    obj->has[key] = true;
    obj->map[key] = obj->size;
    obj->list[obj->size++] = val;
    return true;
}

bool randomizedSetRemove(RandomizedSet* obj, int val) {
    int key = val + CAP;
    if (!obj->has[key]) return false;
    int idx = obj->map[key];
    int last = obj->list[obj->size - 1];
    obj->list[idx] = last;
    obj->map[last + CAP] = idx;
    obj->size--;
    obj->has[key] = false;
    return true;
}

int randomizedSetGetRandom(RandomizedSet* obj) {
    return obj->list[rand() % obj->size];
}

void randomizedSetFree(RandomizedSet* obj) {
    free(obj->list); free(obj);
}

js

var RandomizedSet = function () {
  this.map = new Map() // val -> index
  this.list = []
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.map.has(val)) return false
  this.map.set(val, this.list.length)
  this.list.push(val)
  return true
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.map.has(val)) return false
  const idx = this.map.get(val)
  const last = this.list[this.list.length - 1]
  this.list[idx] = last
  this.map.set(last, idx)
  this.list.pop()
  this.map.delete(val)
  return true
}

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  return this.list[Math.floor(Math.random() * this.list.length)]
}

py

class RandomizedSet:
    def __init__(self):
        self.map = {}  # val -> index
        self.list = []

    def insert(self, val: int) -> bool:
        if val in self.map:
            return False
        self.map[val] = len(self.list)
        self.list.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.map:
            return False
        idx = self.map[val]
        last = self.list[-1]
        self.list[idx] = last
        self.map[last] = idx
        self.list.pop()
        del self.map[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)

• 时间复杂度：所有操作均为 $O(1)$
• 空间复杂度：$O(n)$

算法思路：

• 哈希表存储值到索引的映射，数组存储元素
• 删除时将目标元素与末尾交换后 pop，保证 $O(1)$
• getRandom 直接随机索引数组