380. O(1) 時間插入、刪除和獲取隨機元素

實現(xiàn)RandomizedSet 類：

RandomizedSet() 初始化 RandomizedSet 對象

bool insert(int val) 當元素 val 不存在時，向集合中插入該項，并返回 true ；否則，返回 false 。

bool remove(int val) 當元素 val 存在時，從集合中移除該項，并返回 true ；否則，返回 false 。

int getRandom() 隨機返回現(xiàn)有集合中的一項（測試用例保證調(diào)用此方法時集合中至少存在一個元素）。每個元素應(yīng)該有 相同的概率 被返回。

你必須實現(xiàn)類的所有函數(shù)，并滿足每個函數(shù)的 平均 時間復(fù)雜度為 O(1) 。

?

示例：

輸入

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], [1], [2], [2], [], [1], [2], []]

輸出

[null, true, false, true, 2, true, false, 2]

解釋

RandomizedSet randomizedSet = new RandomizedSet();

randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。

randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。

randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合現(xiàn)在包含 [1,2] 。

randomizedSet.getRandom(); // getRandom 應(yīng)隨機返回 1 或 2 。

randomizedSet.remove(1); // 從集合中移除 1 ，返回 true 。集合現(xiàn)在包含 [2] 。

randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。

randomizedSet.getRandom(); // 由于 2 是集合中唯一的數(shù)字，getRandom 總是返回 2 。

?

我感覺這道題比較難的是搞清楚字典和列表的操作，我一開始就寫反了！！

字典是可以取任意位置的，O(1)

列表需要O(1)的話則需要只使用push和pop操作，只操作末尾元素

因此在刪除的時候不能直接刪除，而是把列表中最后一位放到要刪除的位子上，然后刪除最后一位~

時間復(fù)雜度低了一點，因為random我直接用的random庫，沒有用choice(）函數(shù)

class?RandomizedSet:

????def?__init__(self):

????????self.nums=[]

????????self.dict=dict()

????def?insert(self,?val:?int)?->?bool:

????????if?val?not?in?self.dict:

????????????self.dict[val]=len(self.nums)

????????????self.nums.append(val)

????????????return?True

????????return?False

????def?remove(self,?val:?int)?->?bool:

????????if?val?in?self.dict:

????????????sw_val=self.nums[-1]

????????????index=self.dict[val]

????????????self.nums[index]=sw_val

????????????self.dict[sw_val]=index

????????????del?self.dict[val]

????????????self.nums.pop()

????????????return?True

????????return?False

????#在列表中，只能對nums尾部的元素進行添加或者刪除的操作，因此在刪除制定位的數(shù)字時，需要把最后一個數(shù)字放到這個數(shù)字的位子上然后刪除最后一個數(shù)字，此時需要更新字典中的鍵值對

????def?getRandom(self)?->?int:

????????if?len(self.nums)==1:return?self.nums[0]

????????else:

????????????ran=random.randint(0,len(self.nums)-1)

????????????return?self.nums[ran]

#?Your?RandomizedSet?object?will?be?instantiated?and?called?as?such:

#?obj?=?RandomizedSet()

#?param_1?=?obj.insert(val)

#?param_2?=?obj.remove(val)

#?param_3?=?obj.getRandom()