Java solution with two HashMaps: easy to understand


  • 9
    Z

    If we assume the operation of HashMap is O(1), then we have the following solution.

    import java.util.Random;
    
    public class RandomizedSet {
        
        private HashMap<Integer, Integer> keyMap = null;
        private HashMap<Integer, Integer> valueMap = null;
        int count;
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            keyMap = new HashMap<Integer, Integer>();
            valueMap = new HashMap<Integer, Integer>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(keyMap.containsKey(val)) {
                return false;
            } else {
                keyMap.put(val, count);
                valueMap.put(count, val);
                count = keyMap.size();
                return true;
            }
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(!keyMap.containsKey(val)) {
                return false;
            } else {
                int valueKey = keyMap.get(val);
                keyMap.remove(val);
                if(valueKey != valueMap.size() - 1) {
                    valueMap.put(valueKey, valueMap.get(valueMap.size() - 1));
                    keyMap.put(valueMap.get(valueMap.size() - 1), valueKey);
                    valueMap.remove(valueMap.size() - 1);
                } else {
                    valueMap.remove(valueKey);
                }
                count = keyMap.size();
                return true;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            Random random = new Random();
            int n = random.nextInt(keyMap.size());
            return valueMap.get(n);
        }
    }
    

  • 1

    @zhouhanjiang Are u sure your getRandom() is O(1)?


  • 1
    Z

    @haruhiku You are right, the iteration will take O(n) time. I changed my code to use two HashMaps, it should be O(1) now.


  • 0
    E

    then why not use hashset directly?


Log in to reply
 

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