題目

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

  • 231 <= val <= 231 - 1
  • At most 2 * 105 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

解釋題目

題目會給一個 RandomizedSet 的類別，要分別寫出三個函式 insert()、remove()、跟 getRandom()。insert() 就是插入一個數值，如果 set() 中沒有該數值，就插入並返回 True，反之如果有該數值就不用插入，返回 False。remove() 則是刪除 set() 中某數值，如果 set() 中沒有該數值，返回 False，反之如果有該數值，就刪除他並返回 True。getRandom() 是要在 set() 中，隨機返回一個數字。

思路

  1. 這題先要知道 set() 跟 dict() 的 remove 都是平均 O(1) 的時間複雜度，而 list 的移除只有在 list.pop() 才是 O(1) 操作，list.remove() 則是 O(n) 操作。

  2. 那很直覺地就會想用 hash map 的方式，只不過在 getRandom() 會無法操作，因為 hash map 沒有索引，沒辦法隨機取得其中的元素。

  3. hash map 的 key 值，是經過 哈希函數 計算後，得到 hash value，然後映射到底層陣列中的索引位置，所以 key 值本身不算索引，且不具順序性，而是透過哈希函數找到 value 值。

  4. 索引 ( index ) 直接對應底層陣列中的存儲位置，無需映射。索引必須是範圍內的整數 0 <= index < len(list)，插入或刪除的話，索引會需要重新排列，是 O(n) 操作，但是 append() 跟 pop() 例外，是屬於 O(1) 操作。

  5. 之所以是 平均 O(1) 的時間複雜度，是因為可能會產生 哈希衝突，哈希衝突是指: 當多個鍵值對都映射到同一槽位，就會發生衝突，會需要在槽位中尋找正確的鍵值對。

    • 假設鍵值對是: 

      1
      hash_map = {"apple": 10, "banana": 20, "cherry": 30}`

    • 計算出的映射槽位如下，最壞的可能就是全部映射到同一槽位，必須要遍歷同一個槽位，才能找到正確的鍵值對，那就會是 O(n) 操作。

      1
      2
      3
      4
      5
      槽位 0: []
      槽位 1: []
      槽位 2: [("apple", 10), ("banana", 20)]
      槽位 3: [("cherry", 30)]
      槽位 4: []

  6. 所以這題關鍵是需要 hash map 跟 list 同時操作，list 主要是給 getRandom 使用，因為有索引。而 hash map 主要是用來紀錄索引值，在 remove 數值時， 需把最後一個元素移到要刪除的元素的位置，透過 list.pop() 移除。同時更改最後一個元素記錄在 hash table 的 index。

  7. 以 data = [ 1, 2, 3 ] 為例，其 pos = { "1": 0, "2": 1, "3": 2 }，如果要刪除某個數值 ( 假設是 val = 2 ) ，就必須:
    (1) 把該數值 = 最後一個數值 ( 也就是 data 中的 2 要等於 3， data 會變成 [ 1, 3, 3 ] )，所以由 pos[val] 找出索引，data[pos[val]] = data[-1]

    (2) 修改最後一位數值的 index 值，使其等於被刪除值的索引值，所以 pos[data[-1]] = pos[val]

  8. 最後要 data.pop() 刪除該值，並刪除其所引 del pos[val]

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class RandomizedSet:

    def __init__(self):
        self.arr = [] 
        self.pos = {}  # 用於記錄數字對應的索引

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.arr.append(val)
        self.pos[val] = len(self.arr) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        
        # 將最後一個元素移到要刪除的元素的位置
        self.arr[self.pos[val]] = self.arr[-1]
        
        # 修改最後一個元素 index
        self.pos[self.arr[-1]] = self.pos[val]
        
        # 刪除最後一個元素
        self.arr.pop()
        del self.pos[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.arr)  # 隨機返回一個數字