跳至主要內容

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

381. O(1) 时间插入、删除和获取随机元素 - 允许重复

🔴 Hard  🔖  设计 数组 哈希表 数学 随机化  🔗 力扣open in new window LeetCodeopen in new window

题目

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element.

Implement the RandomizedCollection class:

  • RandomizedCollection() Initializes the empty RandomizedCollection object.
  • bool insert(int val) Inserts an item val into the multiset, even if the item is already present. Returns true if the item is not present, false otherwise.
  • bool remove(int val) Removes an item val from the multiset if present. Returns true if the item is present, false otherwise. Note that if val has multiple occurrences in the multiset, we only remove one of them.
  • int getRandom() Returns a random element from the current multiset of elements. The probability of each element being returned is linearly related to the number of the same values the multiset contains.

You must implement the functions of the class such that each function works on average O(1) time complexity.

Note: The test cases are generated such that getRandom will only be called if there is at least one item in the RandomizedCollection.

Example 1:

Input

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]

[[], [1], [1], [2], [], [1], []]

Output

[null, true, false, true, 2, true, 1]

Explanation

RandomizedCollection randomizedCollection = new RandomizedCollection();

randomizedCollection.insert(1); // return true since the collection does not contain 1.

// Inserts 1 into the collection.

randomizedCollection.insert(1); // return false since the collection contains 1.

// Inserts another 1 into the collection. Collection now contains [1,1].

randomizedCollection.insert(2); // return true since the collection does not contain 2.

// Inserts 2 into the collection. Collection now contains [1,1,2].

randomizedCollection.getRandom(); // getRandom should:

// - return 1 with probability 2/3, or

// - return 2 with probability 1/3.

randomizedCollection.remove(1); // return true since the collection contains 1.

// Removes 1 from the collection. Collection now contains [1,2].

randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls in total will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

题目大意

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。

实现 RandomizedCollection 类:

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

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

注意： 生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。

示例 1:

输入

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]

[[], [1], [1], [2], [], [1], []]

输出

[null, true, false, true, 2, true, 1]

解释

RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。

collection.insert(1); // 返回 true，因为集合不包含 1。

// 将 1 插入到集合中。

collection.insert(1); // 返回 false，因为集合包含 1。

// 将另一个 1 插入到集合中。集合现在包含 [1,1]。

collection.insert(2); // 返回 true，因为集合不包含 2。

// 将 2 插入到集合中。集合现在包含 [1,1,2]。

collection.getRandom(); // getRandom 应当:

// 有 2/3 的概率返回 1,

// 1/3 的概率返回 2。

collection.remove(1); // 返回 true，因为集合包含 1。

// 从集合中移除 1。集合现在包含 [1,2]。

collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。

提示:

  • -2^31 <= val <= 2^31 - 1
  • insert, remove 和 getRandom 最多 总共 被调用 2 * 10^5 次
  • 当调用 getRandom 时，数据结构中 至少有一个 元素

解题思路

我们需要支持 O(1) 的插入、删除和随机访问，因此采用：

  • 数组 elements：用于存储所有插入的元素，方便 getRandom() 通过索引 O(1) 获取随机元素。
  • 哈希表 indicesMap（Map<number, Set<number>>）：
    • key: 存储元素值
    • value: 该值在数组 elements 中的所有索引集合（Set）。
    • 为什么用 Set? 允许相同的 val 多次插入，并且删除操作仍然保持 O(1) 复杂度。

1. insert(val)

  1. 先检查 val 是否已经存在于 indicesMap。
  2. 将 val 添加到 elements 数组的 末尾。
  3. 在 indicesMap 里 记录索引：
    • 如果 val 不存在，创建 Set 存储索引。
    • 如果 val 已存在，直接将新索引加入 Set。
  4. 返回 val 是否是第一次插入（true 或 false）。
  • 时间复杂度：O(1)，因为 数组 push 和 Map 操作 皆为 O(1)。

2. remove(val)

  1. 先检查 val 是否存在于 indicesMap，如果不存在直接返回 false。
  2. 找到 val 在数组中的某个索引 removeIndex。
  3. 获取 elements 最后一个元素 lastElement，准备 将其移动到 removeIndex 位置（避免数组 splice 操作，保证 O(1)）。
  4. 替换 val
    • elements[removeIndex] = lastElement （将最后一个元素移动到 val 的位置）
    • elements.pop() 删除最后一个元素
  5. 更新 indicesMap
    • 删除 removeIndex，如果 val 没有索引了，从 Map 中删除。
    • 更新 lastElement 的索引（如果 lastElement 不是 val 本身）。
  6. 返回 true，表示成功删除。
  • 时间复杂度：O(1)，因为：
    • 获取索引是 O(1) (Set.values().next().value)
    • 替换索引是 O(1)
    • elements.pop() 是 O(1)
    • Map 操作是 O(1)

3. getRandom()

  1. 生成 [0, elements.length - 1] 之间的随机索引。
  2. 返回 elements[randomIndex]。
  • 时间复杂度：O(1)，因为数组随机访问是 O(1)。

复杂度分析

  • 时间复杂度：O(1)， insert, remove 和 getRandom 都是O(1)时间复杂度。
  • 空间复杂度：O(n)，使用了一个数组和一个哈希表存储元素及其索引。

代码

class RandomizedCollection {
	constructor() {
		this.elements = []; // 存储所有插入的元素
		this.indicesMap = new Map(); // Map<number, Set<number>>，存储每个值的索引集合
	}

	/**
	 * 插入一个值到集合中
	 * @param {number} val
	 * @return {boolean} 是否是第一次插入
	 */
	insert(val) {
		const exists = this.indicesMap.has(val); // 记录 val 是否已经存在
		this.elements.push(val); // 将 val 添加到数组末尾

		// 在哈希表中记录 val 对应的索引
		if (!exists) {
			this.indicesMap.set(val, new Set());
		}
		this.indicesMap.get(val).add(this.elements.length - 1);

		return !exists;
	}

	/**
	 * 从集合中删除一个值
	 * @param {number} val
	 * @return {boolean} 是否删除成功
	 */
	remove(val) {
		if (!this.indicesMap.has(val)) return false; // 若 val 不存在，直接返回 false

		const lastIndex = this.elements.length - 1; // 获取数组最后一个元素的索引
		const valIndices = this.indicesMap.get(val); // 获取 val 所在的索引集合
		const removeIndex = valIndices.values().next().value; // 取出 val 在数组中的某个索引

		const lastElement = this.elements[lastIndex]; // 获取数组的最后一个元素
		this.elements[removeIndex] = lastElement; // 用最后一个元素覆盖待删除元素
		this.elements.pop(); // 删除数组最后一个元素

		// 更新 val 的索引集合
		valIndices.delete(removeIndex);
		if (valIndices.size === 0) this.indicesMap.delete(val); // 若 val 没有索引了，从 Map 中删除

		// 若被替换的元素 lastElement 不是 val，则需要更新 lastElement 的索引
		if (removeIndex !== lastIndex) {
			const lastIndices = this.indicesMap.get(lastElement);
			lastIndices.delete(lastIndex);
			lastIndices.add(removeIndex); // 更新 lastElement 在数组中的位置
		}

		return true;
	}

	/**
	 * 随机获取一个元素
	 * @return {number} 随机返回集合中的一个元素
	 */
	getRandom() {
		const randomIndex = Math.floor(Math.random() * this.elements.length);
		return this.elements[randomIndex];
	}
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

相关题目

题号标题题解标签难度力扣
380O(1) 时间插入、删除和获取随机元素[✓]设计 数组 哈希表 2+🟠🀄️open in new window 🔗open in new window
Copyright © 2025 2xiao