题目描述
解题思路
-
我们具有两个平均插入时间为O(1) 的选择，哈希表和数组。
-
虽然哈希表提供常数时间的插入和删除，但是实现 getRandom 时会出现问题。哈希表中没有索引，因此要获得真正的随机值，则要将哈希表中的键转换为列表，这需要线性时间，解决的方法是用一个列表存储值，并在该列表中实现常数时间的 getRandom。
-
列表有索引可以实现常数时间的 insert 和 getRandom，则接下来的问题是如何实现常数时间的 remove。可以采用哈希表存储值对应的索引，随机删除的时候通过哈希表获取索引值，然后和列表最后一个元素进行交换，然后删除列表最后一个元素，不涉及到数组中元素的移动，因此在常数时间下即可完成，同时更新哈希表索引信息，从而实现O（1）复杂度下的随机删除。
解题代码
/**
* @description:
* @author: lilang
* @version:
* @modified By:1170370113@qq.com
*/
public class RandomizedSet {
HashMap<Integer, Integer> dict;
ArrayList<Integer> list;
Random rand = new Random();
public RandomizedSet() {
list = new ArrayList<>();
dict = new HashMap<>();
}
public boolean insert(int val) {
if (dict.containsKey(val)) {
return false;
}
dict.put(val, list.size());
list.add(val);
return true;
}
public boolean remove(int val) {
if (!dict.containsKey(val)) {
return false;
}
int lastVal = list.get(list.size() - 1);
int valIndex = dict.get(val);
list.set(valIndex, lastVal);
dict.put(lastVal, valIndex);
list.remove(list.size() - 1);
dict.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
