1、前言
题目描述2、思路
将最后一个元素放到移除元素的位置上,然后把最后一个元素删除就行,还要考虑最后一个是第一个情况
3、代码
class RandomizedSet {
private Map<Integer, Integer> map = new HashMap<>();
private List<Integer> list = new ArrayList<>();
private Random random = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if(map.containsKey(val)){
return false;
}
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
// 将最后一个元素放到移除元素的位置上,
// 然后把最后一个元素删除就行
// 还要考虑最后一个是第一个情况
int removeIndex = map.get(val);
int lastIndex = list.size() - 1;
int lastVal = list.get(lastIndex);
list.set(removeIndex, lastVal);
map.put(lastVal, removeIndex);
list.remove(lastIndex);
map.remove(val);
return true;
}
public int getRandom() {
int index = random.nextInt(list.size());
return list.get(index);
}
}
网友评论