Few Changes From GetRandom O(1) -- ArrayList && HashMap Solution


  • 0

    Based on the solution from the LC380, I come up with this solution with some helpful comments...

    public class RandomizedCollection {
        
        List<Integer> list; //store number
        Map<Integer, Set<Integer>> map; // <Number, Position>
        
    
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            list = new ArrayList<>();
            map = new HashMap<>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean isContain = map.containsKey(val);
            if(!isContain)
                map.put(val, new HashSet<>());
            map.get(val).add(list.size());
            list.add(val);
            return !isContain;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val))
                return false;
            if(!map.get(val).contains(list.size() - 1)) {
                //get the location of the element
                int location = map.get(val).iterator().next();
                //remove the location in the set
                map.get(val).remove(location);
                //get the last element in the list
                int last = list.get(list.size() - 1);
                //set the last element in the location
                list.set(location, last);
                //update the location of the last element
                map.get(last).remove(list.size() - 1);
                map.get(last).add(location);
            }
            else{
                map.get(val).remove(list.size() - 1);
            }
            //if empty set, remove the key-value pair from the map
            if(map.get(val).isEmpty())
                map.remove(val);
            //remove the last element in the list
            list.remove(list.size() - 1);
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get((int)(Math.random() * list.size()));
        }
    }
    
    /**
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

    Hope that will help.


Log in to reply
 

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