题目
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
分析
设计一个数据结构，对于三种基础操作平均时间复杂度为O(1)，插入、删除和随机获取某一个元素。
随机获取某个元素，可以用一个List存放所有的数据，用java.util.Random函数选取一个Index输出。
插入也可以直接插入到这个List的末尾。
但是删除的时候就不能保证是O(1)的时间复杂度了。因为如果只有一个List可用，查找O(n)，删除移动也有O(n)。
为了解决删除的问题，加一个map记录元素和元素在List中的位置，要删除时可以通过这个map将查找时间缩小到O(1)，为了防止删除移动和保证插入操作的简单一致性（插到末尾），每次只删除最后一个位置的元素，如果要删的元素不在这个位置，则将最后一个位置的元素与这个元素调换，再进行删除。
这个版本是不允许有重复记录的，下一题会讲怎么处理允许重复记录的情况。
代码
class RandomizedSet {
private List<Integer> list;
private Map<Integer, Integer> map;
java.util.Random rand = new java.util.Random();
/** Initialize your data structure here. */
public RandomizedSet() {
list = new ArrayList();
map = new HashMap();
}
/** 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) {
//从map中删除
if(!map.containsKey(val)) return false;
int index = map.get(val);
map.remove(val);
if(index != list.size() - 1){ //不是最后一个需要跟最后一个调换位置
int lastValue = list.get(list.size() - 1);
list.set(index, lastValue); //改变list位置
map.put(lastValue, index); //改变map记录
}
list.remove(list.size() - 1);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(rand.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();
*/
