0%

[Leetcode]381. Insert Delete GetRandom O(1) - Duplicates allowed(C++)

题目描述

题目链接:381. Insert Delete GetRandom O(1) - Duplicates allowed

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the multiset if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the multiset if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current multiset of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the linear probability to the number of same values the multiset contains..

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

例子

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. Inserts 1 to the collection. Returns true as the collection did not contain 1.
randomizedCollection.insert(1); // return False. Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
randomizedCollection.insert(2); // return True. Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
randomizedCollection.getRandom(); // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
randomizedCollection.remove(1); // return True. Removes 1 from the collection, returns true. Collection now contains [1,2].
randomizedCollection.getRandom(); // getRandom should return 1 and 2 both equally likely.

Constraints

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

解题思路

[Leetcode]380. Insert Delete GetRandom O(1)(C++) 的进阶版本,要求数组中可以存在重复数字,因此我们做法类似,但是在存储数组的下标方式需要做出一些调整。从值-值改为值-集合,使得可以存储多个下标。插入和返回随机元素的过程基本不用改变,而在去除元素时,要注意哈希表中值更新的顺序,具体参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <unordered_map>
#include <unordered_set>
#include <vector>

class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {}

/** Inserts a value to the collection. Returns true if the collection did
* not already contain the specified element. */
bool insert(int val) {
bool has_val = (val_indices[val].empty());
val_indices[val].insert(nums.size());
nums.push_back(val);
return has_val;
}

/** Removes a value from the collection. Returns true if the collection
* contained the specified element. */
bool remove(int val) {
if (val_indices[val].size()) {
int index = *val_indices[val].begin();
val_indices[val].erase(index);
int end_num = nums.back();
val_indices[end_num].insert(index);
val_indices[end_num].erase(nums.size() - 1);

std::swap(nums[index], nums.back());
nums.pop_back();
return true;
}
return false;
}

/** Get a random element from the collection. */
int getRandom() { return nums[rand() % nums.size()]; }

private:
std::vector<int> nums;
std::unordered_map<int, std::unordered_set<int>> val_indices;
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 381.InsertDeleteGetRandomO1DuplicatesAllowed.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions