Solution


  • 0
    V
        ArrayList<Integer> randomList;
        Map<Integer, Integer> locMap;
        Random random = new Random();
        
        /** Initialize your data structure here. */
        public RandomizedSet() {
                 randomList = new ArrayList<>();
                 locMap = new HashMap<>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            
            // check if it's in map
            boolean alreadyExists = locMap.containsKey(val);
            if(alreadyExists) {
                return false;
            }
            
            locMap.put(val, randomList.size());
            return randomList.add(val);       
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            boolean exists = locMap.containsKey(val);
            if(!exists) {
                return false;
            }
            int location = locMap.get(val);
            int listSize = randomList.size() -1;
            if(location < listSize) {
                // if the value is not the last one in the list,
            // swap it with last one and then remove the last
                int temp = randomList.get(location);
                int last = randomList.get(listSize);
                randomList.set(location, last );
                //update the map
                locMap.put(last, location);
            }
            randomList.remove(listSize);
            locMap.remove(val);
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            System.out.println(randomList.size());
           return randomList.get(random.nextInt(randomList.size()));
        }
    }
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

Log in to reply
 

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