Insert Delete Get Random With Duplicate All O1 这题一般是让你讲原理不需写。我当时是让我写代码

public class InsertDeleteGetRandomO1DuplicatedAllowed {
HashMap<Integer, HashSet<Integer>> map1;
HashMap<Integer, Integer> map2;
Random r;

public InsertDeleteGetRandomO1DuplicatedAllowed() {
map1 = new HashMap<Integer, HashSet<Integer>>();
map2 = new HashMap<Integer, Integer>();
r = new Random();
}


public boolean insert(int val) {
int size2 = map2.size();
map2.put(size2+1, val);

if(map1.containsKey(val)){
map1.get(val).add(size2+1);
return false;
}else{
HashSet<Integer> set = new HashSet<Integer>();
set.add(size2+1);
map1.put(val, set);
return true;
}
}


public boolean remove(int val) {
if(map1.containsKey(val)){
HashSet<Integer> set = map1.get(val);
int toRemove = set.iterator().next();


set.remove(toRemove);

if(set.size()==0){
map1.remove(val);
}

if(toRemove == map2.size()){
map2.remove(toRemove);
return true;
}

int size2 = map2.size();
int key = map2.get(size2);

HashSet<Integer> setChange = map1.get(key);
setChange.remove(size2);
setChange.add(toRemove);

map2.remove(size2);
map2.remove(toRemove);

map2.put(toRemove, key);

return true;
}

return false;
}


public int getRandom() {
if(map1.size()==0)
return -1;

if(map2.size()==1){
return map2.get(1);
}

return map2.get(r.nextInt(map2.size())+1); // nextInt() returns a random number in [0, n).
}