題目
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.
分析
設(shè)計一個數(shù)據(jù)結(jié)構(gòu)牍疏，對于三種基礎(chǔ)操作平均時間復(fù)雜度為O(1)前弯，插入远寸、刪除和隨機(jī)獲取某一個元素。
隨機(jī)獲取某個元素瞎嬉，可以用一個List存放所有的數(shù)據(jù)，用java.util.Random函數(shù)選取一個Index輸出。
插入也可以直接插入到這個List的末尾风宁。
但是刪除的時候就不能保證是O(1)的時間復(fù)雜度了腐碱。因為如果只有一個List可用誊垢，查找O(n)，刪除移動也有O(n)症见。
為了解決刪除的問題喂走，加一個map記錄元素和元素在List中的位置，要刪除時可以通過這個map將查找時間縮小到O(1)谋作，為了防止刪除移動和保證插入操作的簡單一致性（插到末尾）芋肠，每次只刪除最后一個位置的元素，如果要刪的元素不在這個位置瓷们，則將最后一個位置的元素與這個元素調(diào)換业栅，再進(jìn)行刪除。
這個版本是不允許有重復(fù)記錄的谬晕，下一題會講怎么處理允許重復(fù)記錄的情況碘裕。
代碼
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){ //不是最后一個需要跟最后一個調(diào)換位置
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();
*/
