# Java Solution beats 97%. Totally based on the previous question

• It is almost the same as the previous question, the only difference is now we use a Map<Integer,Set> to store the indexes of the numbers in the array list. We can take advantage of the O(1) add and delete of Set, but we can't realize a get in O(1). So this is the trick of the solution. I just use the previous solution -- RandomizedSet again to make sure all operations are O(1). ---> Map<Integer, RandomizedSet> the key represents the element, value represents all indexes of the key.

/**/
class RandomizedSet {

``````	private List<Integer> list;
private Map<Integer, Integer> position;
private static Random random = new Random();

/* initialzie */
public RandomizedSet() {
list = new ArrayList<Integer>();
position = 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 (position.containsKey(val))
return false;
position.put(val, list.size() - 1);
return true;
}

/* Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!position.containsKey(val))
return false;
int p = position.get(val);
int lastVal = list.get(list.size() - 1);
list.set(p, lastVal);
list.remove(list.size() - 1);
position.put(lastVal, p);
position.remove(val);
return true;
}

/* Get a random element from the set. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}

public int size() {
return list.size();
}

}
``````

public class RandomizedCollection {

``````private static Random random = new Random();
private List<Integer> list;
private Map<Integer, RandomizedSet> positions;

/** Initialize your data structure here. */
public RandomizedCollection() {
list = new ArrayList<Integer>();
positions = new HashMap<Integer, RandomizedSet>();
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
if (positions.containsKey(val)) {
RandomizedSet pVal = positions.get(val);
pVal.insert(list.size() - 1);
return false;
}
else {
RandomizedSet pVal = new RandomizedSet();
pVal.insert(list.size() - 1);
positions.put(val, pVal);
return true;
}
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!positions.containsKey(val))
return false;
if (val == list.get(list.size() - 1)) {
RandomizedSet s = positions.get(val);
s.remove(list.size() - 1);
if (s.size() == 0)
positions.remove(val);
list.remove(list.size() - 1);
return true;
}

RandomizedSet pVal = positions.get(val);
int pDel = pVal.getRandom();
int lastVal = list.get(list.size() - 1);
RandomizedSet pLast = positions.get(lastVal);
pLast.remove(list.size() - 1);
pLast.insert(pDel);
pVal.remove(pDel);
if (pVal.size() == 0)
positions.remove(val);
list.set(pDel, list.get(list.size() - 1));
list.remove(list.size() - 1);
return true;
}

/** Get a random element from the collection. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
``````

}

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