0380. 常數時間插入、刪除和獲取隨機元素 · ttttt

# 0380. 常數時間插入、刪除和獲取隨機元素 ## 題目地址（380. 常數時間插入、刪除和獲取隨機元素） <https://leetcode-cn.com/problems/insert-delete-getrandom-o1/> ## 題目描述 ``` <pre class="calibre18">``` 設計一個支持在平均時間復雜度 O(1) 下，執行以下操作的數據結構。 insert(val)：當元素 val 不存在時，向集合中插入該項。 remove(val)：元素 val 存在時，從集合中移除該項。 getRandom：隨機返回現有集合中的一項。每個元素應該有相同的概率被返回。示例 : // 初始化一個空的集合。 RandomizedSet randomSet = new RandomizedSet(); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。 randomSet.insert(1); // 返回 false ，表示集合中不存在 2 。 randomSet.remove(2); // 向集合中插入 2 。返回 true 。集合現在包含 [1,2] 。 randomSet.insert(2); // getRandom 應隨機返回 1 或 2 。 randomSet.getRandom(); // 從集合中移除 1 ，返回 true 。集合現在包含 [2] 。 randomSet.remove(1); // 2 已在集合中，所以返回 false 。 randomSet.insert(2); // 由于 2 是集合中唯一的數字，getRandom 總是返回 2 。 randomSet.getRandom(); ``` ``` ## 前置知識 - 數組 - 哈希表 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路這是一個設計題。這道題的核心就是考察基本數據結構和算法的操作以及復雜度。我們來回顧一下基礎知識： - 數組支持隨機訪問，其按照索引查詢的時間復雜度為O(1)O(1)O(1),按值查詢的時間復雜度為O(N)O(N)O(N)，而插入和刪除的時間復雜度為O(N)O(N)O(N)。 - 鏈表不支持隨機訪問，其查詢的時間復雜度為O(N)O(N)O(N),但是對于插入和刪除的復雜度為O(1)O(1)O(1)（不考慮找到選要處理的節點花費的時間）。 - 對于哈希表，正常情況下其查詢復雜度平均為O(N)O(N)O(N)，插入和刪除的復雜度為O(1)O(1)O(1)。由于題目要求 getRandom 返回要隨機并且要在O(1)O(1)O(1)復雜度內，那么如果單純使用鏈表或者哈希表肯定是不行的。而又由于對于插入和刪除也需要復雜度為O(1)O(1)O(1)，因此單純使用數組也是不行的，因此考慮多種使用數據結構來實現。 > 實際上 LeetCode 設計題，幾乎沒有單純一個數據結構搞定的，基本都需要多種數據結構結合，這個時候需要你對各種數據結構以及其基本算法的復雜度有著清晰的認知。對于 getRandom 用數組很簡單。對于判斷是否已經有了存在的元素，我們使用哈希表也很容易做到。因此我們可以將數組隨機訪問，以及哈希表O(1)O(1)O(1)按檢索值的特性結合起來，即同時使用這兩種數據結構。對于刪除和插入，我們需要一些技巧。對于插入： - 我們直接往 append，并將其插入哈希表即可。 - 對于刪除，我們需要做到 O(1)。刪除哈希表很明顯可以，但是對于數組，平均時間復雜度為 O(1)。因此如何應付刪除的這種性能開銷呢？我們知道對于數據刪除，我們的時間復雜度來源于 1. `查找到要刪除的元素` 2. 以及`重新排列被刪除元素后面的元素`。對于 1，我們可以通過哈希表來實現。 key 是插入的數字，value 是數組對應的索引。刪除的時候我們根據 key 反查出索引就可以快速找到。 > 題目說明了不會存在重復元素，所以我們可以這么做。思考一下，如果沒有這個限制會怎么樣？對于 2，我們可以通過和數組最后一項進行交換的方式來實現，這樣就避免了數據移動。同時數組其他項的索引仍然保持不變，非常好！ > 相應地，我們插入的時候，需要維護哈希表圖解：以依次【1，2，3，4】之后為初始狀態，那么此時狀態是這樣的： ![](https://img.kancloud.cn/1e/02/1e02de980d3e8045fd7bf7c3aa449322_796x1186.jpg) 而當要插入一個新的5的時候，我們只需要分別向數組末尾和哈希表中插入這條記錄即可。 ![](https://img.kancloud.cn/56/95/5695eee86be7f1d1a7d3d802c2caf1d6_630x1186.jpg) 而刪除的時候稍微有一點復雜： ![](https://img.kancloud.cn/3c/dd/3cdd7ef50b97b2580b3d485efe45651d_1266x1080.jpg) ## 關鍵點解析 - 數組 - 哈希表 - 數組 + 哈希表 - 基本算法時間復雜度分析 ## 代碼 ``` <pre class="calibre18">``` from random import random class RandomizedSet: def __init__(self): """ Initialize your data structure here. """ self.data = dict() self.arr = [] self.n = 0 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.data: return False self.data[val] = self.n self.arr.append(val) self.n += 1 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 not in self.data: return False i = self.data[val] # 更新data self.data[self.arr[-1]] = i self.data.pop(val) # 更新arr self.arr[i] = self.arr[-1] # 刪除最后一項 self.arr.pop() self.n -= 1 return True def getRandom(self) -> int: """ Get a random element from the set. """ return self.arr[int(random() * self.n)] # 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() ``` ``` ***復雜度分析*** - 時間復雜度：O(1)O(1)O(1) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經30K star啦。大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的LeetCode題解 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)