List<Integer> list;
Map<Integer,Integer> map;//记录元素及其下标
int idx;//下一个插入位置
public RandomizedSet() {
list=new ArrayList<>();
map=new HashMap<>();
idx=0;
}
public boolean insert(int val) {
if(map.containsKey(val))
return false;
list.add(val);
map.put(val,idx++);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val))
return false;
list.set(map.get(val),list.get(list.size()-1));//将最后一个移到val的位置
map.put(list.get(idx-1),map.get(val));//更新map的val的值
map.remove(val);
list.remove(idx--);
return true;
}
public int getRandom() {
Random r=new Random();
return list.get(r.nextInt(idx));
}
|
