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

• 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<>());
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);
}
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.

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