Medium

题目描述

实现 RandomizedSet 类：

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

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

示例 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³¹ <= val <= 2³¹ - 1
  • 最多调用 insert、remove 和 getRandom 函数 2 * 10⁵ 次
  • 在调用 getRandom 时，数据结构中至少存在一个元素

解题思路

解题思路

要实现 O(1) 时间复杂度的插入、删除和随机获取元素，关键在于选择合适的数据结构组合。

核心思路：动态数组 + 哈希表

  1. 动态数组：存储所有元素，支持 O(1) 时间的随机访问
  2. 哈希表：存储元素值到数组索引的映射，支持 O(1) 时间的查找

具体实现：

  • 插入：先检查元素是否已存在，若不存在则添加到数组末尾，并在哈希表中记录其索引
  • 删除：关键在于如何保持 O(1) 复杂度。不能直接删除数组中间元素（会导致 O(n) 的移动操作），而是采用交换删除法：
    1. 将要删除的元素与数组最后一个元素交换
    2. 删除数组最后一个元素
    3. 更新哈希表中相关元素的索引映射
  • 随机获取：生成随机索引，直接访问数组对应位置

这种设计巧妙地利用了数组的随机访问特性和哈希表的快速查找特性，同时通过交换删除法避免了数组元素移动的开销。

代码实现

class RandomizedSet {
private:
    vector<int> nums;
    unordered_map<int, int> valToIndex;
    
public:
    RandomizedSet() {
        
    }
    
    bool insert(int val) {
        if (valToIndex.find(val) != valToIndex.end()) {
            return false;
        }
        valToIndex[val] = nums.size();
        nums.push_back(val);
        return true;
    }
    
    bool remove(int val) {
        if (valToIndex.find(val) == valToIndex.end()) {
            return false;
        }
        int index = valToIndex[val];
        int lastElement = nums.back();
        
        nums[index] = lastElement;
        valToIndex[lastElement] = index;
        
        nums.pop_back();
        valToIndex.erase(val);
        return true;
    }
    
    int getRandom() {
        int randomIndex = rand() % nums.size();
        return nums[randomIndex];
    }
};

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.val_to_index = {}

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

    def remove(self, val: int) -> bool:
        if val not in self.val_to_index:
            return False
        
        index = self.val_to_index[val]
        last_element = self.nums[-1]
        
        self.nums[index] = last_element
        self.val_to_index[last_element] = index
        
        self.nums.pop()
        del self.val_to_index[val]
        return True

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

public class RandomizedSet {
    private List<int> nums;
    private Dictionary<int, int> valToIndex;
    private Random rand;

    public RandomizedSet() {
        nums = new List<int>();
        valToIndex = new Dictionary<int, int>();
        rand = new Random();
    }
    
    public bool Insert(int val) {
        if (valToIndex.ContainsKey(val)) {
            return false;
        }
        valToIndex[val] = nums.Count;
        nums.Add(val);
        return true;
    }
    
    public bool Remove(int val) {
        if (!valToIndex.ContainsKey(val)) {
            return false;
        }
        
        int index = valToIndex[val];
        int lastElement = nums[nums.Count - 1];
        
        nums[index] = lastElement;
        valToIndex[lastElement] = index;
        
        nums.RemoveAt(nums.Count - 1);
        valToIndex.Remove(val);
        return true;
    }
    
    public int GetRandom() {
        int randomIndex = rand.Next(nums.Count);
        return nums[randomIndex];
    }
}

var RandomizedSet = function() {
    this.nums = [];
    this.valToIndex = new Map();
};

RandomizedSet.prototype.insert = function(val) {
    if (this.valToIndex.has(val)) {
        return false;
    }
    this.valToIndex.set(val, this.nums.length);
    this.nums.push(val);
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    if (!this.valToIndex.has(val)) {
        return false;
    }
    
    const index = this.valToIndex.get(val);
    const lastElement = this.nums[this.nums.length - 1];
    
    this.nums[index] = lastElement;
    this.valToIndex.set(lastElement, index);
    
    this.nums.pop();
    this.valToIndex.delete(val);
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    const randomIndex = Math.floor(Math.random() * this.nums.length);
    return this.nums[randomIndex];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
insertO(1) 平均-
removeO(1) 平均-
getRandomO(1)-
整体空间-O(n)

说明：

  • 时间复杂度：所有操作都是 O(1) 平均时间复杂度。哈希表操作在最坏情况下可能是 O(n)，但平均情况下是 O(1)
  • 空间复杂度：需要存储 n 个元素的动态数组和哈希表，总空间复杂度为 O(n)

相关题目