C# solution using Dictionary and HashSet (298ms)


  • 0
    E

    This solution also uses the magic of LINQ's first() function to basically get a random value from the HashSet

            public class RandomizedCollection {
    
                Dictionary<int, int> _randomSet;
                Dictionary<int, HashSet<int>> _inverseRandomSet;
                int _counter;
                Random _random;
                /** Initialize your data structure here. */
                public RandomizedCollection() {
                    _randomSet = new Dictionary<int, int>();
                    _inverseRandomSet = new Dictionary<int, HashSet<int>>();
                    _random = new Random();
                    _counter = 0;
                }
    
                /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
                public bool Insert(int val) {
                    if (_inverseRandomSet.ContainsKey(val)) {
                        _inverseRandomSet[val].Add(_counter);
                        _randomSet.Add(_counter, val);
                        _counter++;
                        return false;
                    }
                    _randomSet.Add(_counter, val);
                    _inverseRandomSet.Add(val, new HashSet<int>());
                    _inverseRandomSet[val].Add(_counter);
                    _counter++;
                    return true;
                }
    
                /** Removes a value from the set. Returns true if the set contained the specified element. */
                public bool Remove(int val) {
                    if (!_inverseRandomSet.ContainsKey(val)) {
                        return false;
                    }
                    var randomSetIndex = _inverseRandomSet[val].First();
                    _inverseRandomSet[val].Remove(randomSetIndex);
                    if (_inverseRandomSet[val].Count == 0) {
                        _inverseRandomSet.Remove(val);
                    }
                    _randomSet.Remove(randomSetIndex);
                    if (_counter - 1 != randomSetIndex) {
                        MoveIndex(_counter - 1, randomSetIndex);
                    }
                    _counter--;
                    return true;
                }
    
                /** Get a random element from the set. */
                public int GetRandom() {
                    var index = _random.Next(_counter);
                    return _randomSet[index];
                }
    
                private void MoveIndex(int from, int to) {
                    var val = _randomSet[from];
                    _randomSet.Remove(from);
                    _randomSet.Add(to, val);
                    _inverseRandomSet[val].Remove(from);
                    _inverseRandomSet[val].Add(to);
                }
            }
    

    Explanation is that basically, the _randomSet contains all the counter to values for taking a random entry while _inverseRandomSet contains values mapping to where it is in the _randomSet Dictionary.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.