Clean Java Solution using HashMap and ArrayList - 114ms


  • 0
    J
    public class RandomizedCollection {
        Map<Integer, Set<Integer>> myMap;
        List<Integer> data;
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            myMap = new HashMap<>();
            data = new ArrayList<>();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            Set<Integer> indexSet = myMap.get(val);
            if (indexSet == null) { // val is not contained in data
                // add val to data
                data.add(val);
                // update myMap
                indexSet = new HashSet<>();
                indexSet.add(data.size() - 1);
                myMap.put(val, indexSet);
                return true;
            } else { // val has already existed in data
                data.add(val);
                indexSet.add(data.size() - 1);
                return false;
            }
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            Set<Integer> indexSet = myMap.get(val);
            if (indexSet == null) {
                return false;
            } else {
                int valIndex = indexSet.iterator().next();
                // Step 1: Remove val from indexSet.
                // First, swap the last element in data with lastIndex
                int valueInData = data.get(data.size() - 1);
                data.set(valIndex, valueInData);
                // Then, remove val from indexSet.
                indexSet.remove(valIndex);
                // Step 2: update info of valueInData in myMap
                Set<Integer> valueInDataSet = myMap.get(valueInData);
                if (valueInDataSet.remove(data.size() - 1)) {
                    valueInDataSet.add(valIndex);
                }
                // Step 3: remove the last val from data
                data.remove(data.size() - 1);
                // also, if indexSet is empty now, clean it up.
                if (indexSet.isEmpty()) {
                    myMap.remove(val);
                }
                return true;
            }
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return data.get((int)(Math.random() * data.size()));
        }
    }
    
    

Log in to reply
 

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