Java solution using two HashMaps (113 ms)


  • 0
    T
    public class RandomizedSet {
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            hash = new HashMap<Integer, Integer>();
            reverseHash = new HashMap<Integer, Integer>();
            maxValue = 0;
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(hash.containsKey(val)) return false;
            Integer key = new Integer(val);
            Integer value = new Integer(maxValue);
            hash.put(key, value);
            reverseHash.put(value, key);
            maxValue++;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(!hash.containsKey(val)) return false;
            Integer value = hash.get(val);
            hash.remove(val);
            reverseHash.remove(value);
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            int rand = (int)(Math.random() * maxValue);
            while(!reverseHash.containsKey(rand)) {
                rand = (int)(Math.random() * maxValue);
            }
            return reverseHash.get(rand);
        }
        
        HashMap<Integer, Integer> hash;        
        HashMap<Integer, Integer> reverseHash;
        int maxValue;
    }
    

    The idea is that we keep two hashmaps, and they have opposite key-value relationship. The key in HashMap A is the value in HashMap B, and the value in HashMap A is the key in HashMap B. We arbitrarily set the value in A as the number of elements added to the HashMap before, i.e., maxValue in the code. Hence, each key corresponds to one value, and each value also corresponds to one key. Finally, we randomly choose one integer in [0, maxValue], if we could find a matched key, return it, or we get a random integer again.

    Notice that the worst case running time for getRandom() is not O(1)!


Log in to reply
 

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