380. Insert Delete GetRandom O(1)
要实现所有操作O(1)时间，分析：
Insert O(1): 用 hashmap
Delete O(1): 用 hashmap
GetRandom O(1): 用 array (无法从hashmap中以O(1)时间拿到随机数，所以要用array可以O(1)时间)
总结：(题解摘抄): 利用一个一维数组和一个 HashMap，其中数组用来保存数字，HashMap 用来建立每个数字和其在数组中的位置之间的映射。
class RandomizedSet {
private Map<Integer, Integer> map;
private List<Integer> list;
/** Initialize your data structure here. */
public RandomizedSet() {
map = new HashMap<>();
list = 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;
}
map.put(val, list.size());
list.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;
}
int index = map.get(val);
int lastVal = list.get(list.size() - 1);
map.put(lastVal, index);
list.set(index, lastVal); // updates the element of specified index with the given element
map.remove(val);
list.remove(list.size() - 1);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Random random = new Random();
return list.get(random.nextInt(list.size()));
}
}
/**
* 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();
*/