Sponsored
Sponsored
This approach uses a HashMap to store the indices of elements and a List to store the elements themselves. The HashMap enables quick updates for insertions and deletions, while the List ensures that we can select a random element efficiently.
We maintain a Count of all elements using a map, where each element maps to a set of indices in the List. During removal, we swap the element with the last element in the list (if not already last), update the HashMap accordingly, and remove the last entry from the list for O(1) complexity.
Time Complexity: O(1) average for all operations.
Space Complexity: O(n), where n is the number of elements in the multiset.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4#include <algorithm>
5#include <cstdlib>
6
7class RandomizedCollection {
8public:
9 RandomizedCollection() {}
10
11 bool insert(int val) {
12 bool contained = indexMap.find(val) != indexMap.end();
13 indexMap[val].insert(nums.size());
14 nums.push_back(val);
15 return !contained;
16 }
17
18 bool remove(int val) {
19 if (indexMap.find(val) == indexMap.end() || indexMap[val].empty())
20 return false;
21 int removeIndex = *(indexMap[val].begin());
22 indexMap[val].erase(removeIndex);
23 int lastNum = nums.back();
24 nums[removeIndex] = lastNum;
25 indexMap[lastNum].insert(removeIndex);
26 indexMap[lastNum].erase(nums.size() - 1);
27 nums.pop_back();
28 if (indexMap[val].empty())
29 indexMap.erase(val);
30 return true;
31 }
32
33 int getRandom() {
34 int randomIndex = rand() % nums.size();
35 return nums[randomIndex];
36 }
37
38private:
39 std::vector<int> nums;
40 std::unordered_map<int, std::unordered_set<int>> indexMap;
41};The C++ solution employs a vector for number storage and an unordered map to track indices for efficient access and updates. Insertions and removals are done to maintain O(1) complexity by manipulating the end of the list. Random access is handled using a modulo on the size of the vector.