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.
1using System;
2using System.Collections.Generic;
3
4public class RandomizedCollection {
5 private List<int> nums;
6 private Dictionary<int, HashSet<int>> indexMap;
7 private Random rand;
8
9 public RandomizedCollection() {
10 nums = new List<int>();
11 indexMap = new Dictionary<int, HashSet<int>>();
12 rand = new Random();
13 }
14
15 public bool Insert(int val) {
16 if (!indexMap.ContainsKey(val))
17 indexMap[val] = new HashSet<int>();
18 indexMap[val].Add(nums.Count);
19 nums.Add(val);
20 return indexMap[val].Count == 1;
21 }
22
23 public bool Remove(int val) {
24 if (!indexMap.ContainsKey(val) || indexMap[val].Count == 0)
25 return false;
26 int removeIndex = indexMap[val].First();
27 indexMap[val].Remove(removeIndex);
28 int lastNum = nums[nums.Count - 1];
29 nums[removeIndex] = lastNum;
30 indexMap[lastNum].Add(removeIndex);
31 indexMap[lastNum].Remove(nums.Count - 1);
32 nums.RemoveAt(nums.Count - 1);
33 if (indexMap[val].Count == 0)
34 indexMap.Remove(val);
35 return true;
36 }
37
38 public int GetRandom() {
39 return nums[rand.Next(nums.Count)];
40 }
41}The C# solution mirrors the logic of C++, using a List for element storage and a Dictionary for index tracking. The Random class is utilized to ensure random access, while ensuring all operations maintain average O(1) complexity.