[剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器](剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器 - 力扣(LeetCode) (leetcode-cn.com))
思路
- 一个hashmap 存放 <值,该值存放位置>的映射,一个动态数组ArrayList存放顺序存放该值。
代码
class RandomizedSet {
HashMap<Integer,Integer> map; //键存元素val,值存位置。
ArrayList<Integer> loc;//把元素顺序存入动态数组中
/** Initialize your data structure here. */
public RandomizedSet() {//构造函数
map = new HashMap<>();
loc = new ArrayList<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)) return false; //如果已经包含val,则不能再插入
map.put(val,loc.size());
loc.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)) return false; //如果不包含val,直接返回false
int location = map.get(val);//找到val存放的位置
map.put(loc.get(loc.size()-1),location);//将动态数组loc的最后一个值放入val存放的位置
map.remove(val);//在hashmap中删除键为val的键值对
loc.set(location,loc.get(loc.size()-1));
loc.remove(loc.size()-1);//删除动态数组最后一个值
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Random random = new Random();//创建一个随机变量
int location = random.nextInt(loc.size()); //获取一个随机位置
return loc.get(location);//
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/