如果只有 insert 與 remove 那麼用 hash 系列是比較快的，不過多了 getRandom()，這使 hash 類的不能單獨使用，因為hash類的沒有 sequence 之分。
沒有序列之分，又要隨機，那就得把 hash 轉換成有 squence 的，用隨機抽一個位置。
但與其每次這樣轉換，倒不如多用一個有 squence 的做 val 的存放。更別提轉換會用到 O(N) Time。
要查 val 是否存在？去查 hash 系列的最快。要回隨機值？用有 squence 的再隨機回一個位置最快。
整合起來，val 不僅在有squence的資料類型存在，也要同時存在於hash系列。
以上已經把 insert 跟 getRandom 的注意細節講完，remove會是一個問題。
從hash系列移除 val 那只需要 O(1) Time，但在有squence的呢？要先找到 val 所在的位置才能移除，如果使用內置方法去找，會用O(N) Time，
因為它是從頭依序一個個找。所以，要有一個能保存 該val的位置 ，一查 val 就能得到 位置 的。
順水推舟，hash系列會用 hahsTable，對Python而言是「Dictionary」。
如果在 remove() 中，一查到 val 的位置就刪除，那麼在被刪除的val之後的位置應該也要往前推進，才能保持 Dictionary[val] 總是能正確反映出位置。
但是 Dictionary[val] 並不會隨著 val 在有squence的資料類型被刪除而自動改值，如果由後一個個往前推(即-1)，這過程也會用到 O(N) Time，因為不知道到底影響幾個。
被刪的後面有其它值，會影響甚大。但如果後方沒有任何值，那麼刪除也不會改動到別的位置，也就不必煩惱修改 Dictionary[val] 。
因此先把要被刪除的val與最後一個val作交換，再刪除最後一個，就能在 O(1) Time 完成 remove()。
Python
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.data = list()
self.key = dict()
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.key:
return False
else:
self.key[val] = len(self.data)
self.data.append(val)
return True
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val in self.key:
i = self.key[val]
self.key[self.data[-1]] = i
self.data[i] = self.data[-1]
del self.key[val], self.data[-1]
return True
else:
return False
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return self.data[int(random.random()*len(self.key))]
C#
public class RandomizedSet {
private Dictionary posMap;
private List data;
private Random rand;
/** Initialize your data structure here. */
public RandomizedSet() {
posMap = new Dictionary();
data = new List();
rand = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public bool Insert(int val) {
if (posMap.ContainsKey(val))
{
return false;
}
else
{
posMap[val] = data.Count;
data.Add(val);
}
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public bool Remove(int val) {
if (posMap.ContainsKey(val))
{
int i = posMap[val];
data[i] = data[data.Count-1];
posMap[data[data.Count-1]] = i;
data.RemoveAt(data.Count-1);
posMap.Remove(val);
return true;
}
else
{
return false;
}
}
/** Get a random element from the set. */
public int GetRandom() {
return data[rand.Next(0, data.Count)];
}
}