Java Accepted Solution


  • 0

    The idea is creating corresponse between val and index using two hashmap.

    public class RandomizedSet {
    
        private int size = 0;
        private HashMap<Integer, Integer> num2Index = null;
        private HashMap<Integer, Integer> index2Num = null;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            size = 0;
            num2Index = new HashMap<Integer, Integer>();
            index2Num = 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 (num2Index.containsKey(val)) return false;
            num2Index.put(val, size);
            index2Num.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 (!num2Index.containsKey(val)) return false;
            size--;
            int index = num2Index.get(val);
            num2Index.remove(val);
            if (index == size) {
                index2Num.remove(index);
            } else {
                int num = index2Num.get(size);
                index2Num.remove(size);
                index2Num.replace(index, num);
                num2Index.replace(num, index);
            }
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            Random rand = new Random();
            return index2Num.get(rand.nextInt(size));
        }
    }

Log in to reply
 

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