Insert Delete Get Random All O1 高频题。一般是不写代码只讲有重复，代码写没重复的。我当时是让我写有重复版

高频题。刷熟了很简单，就是交换map2中最后一个元素。重复版类似，用set去重。
public class InsertDeleteGetRandomO1 {
HashMap<Integer, Integer> map1;
HashMap<Integer, Integer> map2;
Random rand;


public InsertDeleteGetRandomO1() {
map1 = new HashMap<Integer, Integer>();
map2 = new HashMap<Integer, Integer>();
rand = new Random(System.currentTimeMillis());
}

public boolean insert(int val) {
if(map1.containsKey(val)){
return false;
}else{
map1.put(val, map1.size());
map2.put(map2.size(), val);
}
return true;
}


public boolean remove(int val) {
if(map1.containsKey(val)){
int index = map1.get(val);
map1.remove(val);
map2.remove(index);
if(map1.size()==0)
return true;

if(index==map1.size())
return true;

int map2_lastE = map2.get(map2.size());
map2.remove(map2.size());
map1.put(map2_lastE, index);
map2.put(index, map2_lastE);
}else{
return false;
}
return true;
}

public int getRandom() {
if(map1.size()==0){
return -1;
}
if(map1.size()==1){
return map2.get(0);
}
return map2.get(new Random().nextInt(map1.size()));
}
}