Use two map, just interesting


  • 0
    W
    public class RandomizedSet {
        private Map<Integer, Integer> map;
        private Map<Integer, Integer> map2;
        private int size;
        final java.util.Random rand;
        
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            map2 = new HashMap<>();
            rand = new java.util.Random();
            size = 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 (map.containsKey(val)) {
                return false;
            }
            
            map.put(val, size);
            map2.put(size, val);
            ++size;
            
            return true; 
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            
            --size;
            int index = map.get(val);
            int last = map2.get(size);
            
            map.put(last, index);
            map.remove(val);
            map2.put(index, last);
            map2.remove(size);
            
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            return map2.get(rand.nextInt(size));
        }
    }
    
    

Log in to reply
 

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