Hard

题目描述

RandomizedCollection 是一个包含数字集合的数据结构，可能包含重复数字（即多重集）。它应该支持插入和删除特定元素，以及报告随机元素。

实现 RandomizedCollection 类：

  • RandomizedCollection() 初始化空的 RandomizedCollection 对象。
  • bool insert(int val) 向多重集中插入元素 val，即使该元素已经存在。如果该元素不存在，则返回 true，否则返回 false。
  • bool remove(int val) 如果存在，则从多重集中删除一个元素 val。如果元素存在，则返回 true，否则返回 false。注意，如果 val 在多重集中出现多次，我们只删除其中一个。
  • int getRandom() 从当前多重集的元素中返回一个随机元素。每个元素被返回的概率与多重集中相同值的数量成线性关系。

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

示例 1：

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

解释
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);   // 返回 true，因为集合不包含 1。插入 1 到集合中。
randomizedCollection.insert(1);   // 返回 false，因为集合包含 1。再插入一个 1 到集合中，集合现在包含 [1,1]。
randomizedCollection.insert(2);   // 返回 true，因为集合不包含 2。插入 2 到集合中，集合现在包含 [1,1,2]。
randomizedCollection.getRandom(); // getRandom 应该：
                                  // - 以 2/3 的概率返回 1，或
                                  // - 以 1/3 的概率返回 2。
randomizedCollection.remove(1);   // 返回 true，因为集合包含 1。从集合中删除 1，集合现在包含 [1,2]。
randomizedCollection.getRandom(); // getRandom 应该返回 1 或 2，概率相等。

提示：

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

解题思路

这道题是经典的数据结构设计题，需要实现一个支持重复元素的随机集合，所有操作都要求 O(1) 平均时间复杂度。

核心思想是使用数组 + 哈希表的组合：

  1. 数组 nums：存储所有元素，支持 O(1) 随机访问
  2. 哈希表 indices：val -> set<int>，记录每个值在数组中的所有位置索引

插入操作：

  • 将元素加入数组末尾
  • 在哈希表中记录该元素的位置
  • 返回值取决于插入前该元素是否存在

删除操作：

  • 找到要删除元素的任意一个位置
  • 将数组最后一个元素移动到该位置（避免数组中间空洞）
  • 更新哈希表中的索引信息
  • 删除数组最后一个元素

随机获取：

  • 直接从数组中随机选择一个位置的元素

关键点在于删除操作的实现：通过将要删除的元素与数组末尾元素交换，然后删除末尾元素，保证数组的连续性，同时维护哈希表中索引的正确性。

由于允许重复元素，每个值可能对应多个索引，所以使用 set 来存储所有位置。

代码实现

class RandomizedCollection {
private:
    vector<int> nums;
    unordered_map<int, unordered_set<int>> indices;
    
public:
    RandomizedCollection() {
        
    }
    
    bool insert(int val) {
        bool notPresent = indices[val].empty();
        nums.push_back(val);
        indices[val].insert(nums.size() - 1);
        return notPresent;
    }
    
    bool remove(int val) {
        if (indices[val].empty()) {
            return false;
        }
        
        int removeIdx = *indices[val].begin();
        int lastElement = nums.back();
        int lastIdx = nums.size() - 1;
        
        nums[removeIdx] = lastElement;
        indices[val].erase(removeIdx);
        indices[lastElement].erase(lastIdx);
        if (removeIdx < lastIdx) {
            indices[lastElement].insert(removeIdx);
        }
        nums.pop_back();
        
        return true;
    }
    
    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

import random
from collections import defaultdict

class RandomizedCollection:

    def __init__(self):
        self.nums = []
        self.indices = defaultdict(set)

    def insert(self, val: int) -> bool:
        not_present = len(self.indices[val]) == 0
        self.nums.append(val)
        self.indices[val].add(len(self.nums) - 1)
        return not_present

    def remove(self, val: int) -> bool:
        if not self.indices[val]:
            return False
        
        remove_idx = self.indices[val].pop()
        last_element = self.nums[-1]
        last_idx = len(self.nums) - 1
        
        self.nums[remove_idx] = last_element
        self.indices[last_element].discard(last_idx)
        if remove_idx < last_idx:
            self.indices[last_element].add(remove_idx)
        self.nums.pop()
        
        return True

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

public class RandomizedCollection {
    private List<int> nums;
    private Dictionary<int, HashSet<int>> indices;
    private Random random;

    public RandomizedCollection() {
        nums = new List<int>();
        indices = new Dictionary<int, HashSet<int>>();
        random = new Random();
    }
    
    public bool Insert(int val) {
        if (!indices.ContainsKey(val)) {
            indices[val] = new HashSet<int>();
        }
        bool notPresent = indices[val].Count == 0;
        nums.Add(val);
        indices[val].Add(nums.Count - 1);
        return notPresent;
    }
    
    public bool Remove(int val) {
        if (!indices.ContainsKey(val) || indices[val].Count == 0) {
            return false;
        }
        
        int removeIdx = indices[val].First();
        int lastElement = nums[nums.Count - 1];
        int lastIdx = nums.Count - 1;
        
        nums[removeIdx] = lastElement;
        indices[val].Remove(removeIdx);
        indices[lastElement].Remove(lastIdx);
        if (removeIdx < lastIdx) {
            indices[lastElement].Add(removeIdx);
        }
        nums.RemoveAt(nums.Count - 1);
        
        return true;
    }
    
    public int GetRandom() {
        return nums[random.Next(nums.Count)];
    }
}

var RandomizedCollection = function() {
    this.vals = [];
    this.indices = new Map();
};

RandomizedCollection.prototype.insert = function(val) {
    const isNew = !this.indices.has(val);
    if (!this.indices.has(val)) {
        this.indices.set(val, new Set());
    }
    this.indices.get(val).add(this.vals.length);
    this.vals.push(val);
    return isNew;
};

RandomizedCollection.prototype.remove = function(val) {
    if (!this.indices.has(val) || this.indices.get(val).size === 0) {
        return false;
    }
    
    const removeIdx = this.indices.get(val).values().next().value;
    const lastVal = this.vals[this.vals.length - 1];
    
    this.vals[removeIdx] = lastVal;
    this.indices.get(val).delete(removeIdx);
    this.indices.get(lastVal).delete(this.vals.length - 1);
    
    if (removeIdx < this.vals.length - 1) {
        this.indices.get(lastVal).add(removeIdx);
    }
    
    this.vals.pop();
    
    if (this.indices.get(val).size === 0) {
        this.indices.delete(val);
    }
    
    return true;
};

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

复杂度分析

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

其中 n 是集合中元素的总数。哈希表操作在平均情况下为 O(1)，set 的插入和删除操作也是 O(1)。

相关题目