Medium
题目要求是Design a data structure that supports all following operations in average O(1) time.难点在于remove的时候如何做到average O(1). 这里用HashMap存val - index pair, 用ArrayList存val. remove()的方法是交换要remove的index和最后一个加入的元素的index，这样可以做到O(1).
class RandomizedSet {
Map<Integer, Integer> valIndexMap;
List<Integer> valList;
/** Initialize your data structure here. */
public RandomizedSet() {
valIndexMap = new HashMap<>();
valList = 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 (valIndexMap.containsKey(val)){
return false;
}
valIndexMap.put(val, valList.size());
valList.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 (!valIndexMap.containsKey(val)){
return false;
}
valIndexMap.put(valList.get(valList.size() - 1), valIndexMap.get(val));
valIndexMap.remove(val);
valList.remove((Integer) val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Random r = new Random();
return valList.get(r.nextInt(valList.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();
*/
