系統設計 設計一個平均O(1)的插入、刪除、隨機選擇元素的資料結構 Leetcode #380

Jess Bailey on Unsplash

題目敘述

題目會給我們一組定義好的界面和需求，要求我們設計一個資料結構，可以滿足平均O(1)的插入元素、刪除元素、隨機取得元素的操作。

RandomizedSet() 類別建構子

bool insert(int val) 插入元素的function界面

bool remove(int val) 刪除元素的function界面

int getRandom() 隨機取得元素的function界面

題目的原文敘述

測試範例

Example 1:

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:

• -2^31 <= val <= 2^31 - 1

所有數值val落在-2^31 ~ 2^31 - 1 之間。

• At most 2 * 105 calls will be made to insert, remove, and getRandom.

對於insert(), revmoe(), getRandom()，做多有2 * 10^5動態測試呼叫。

• There will be at least one element in the data structure when getRandom is called.

題目還保證，呼叫getRandom()時，會確保資料結構裡面至少存在一個元素。

演算法

根據需求的描述，要求平均O(1)的條件，滿直覺就會想到用字典來紀錄或者儲存元素。

比較困難的地方在於，還額外多了一個O(1) getRandom()的要求，相當於強迫我們一定要把每個元素存在一個線性的資料結構裡面，才有機會透過array[index]的方式達到Random access隨機讀取O(1)的要求。

此外，第二個比較特殊的地方在於，刪除的時候，同樣為了滿足O(1) remove()的要求，會先把被刪除的元素先交換到array的尾端，再用pop的方式刪除掉。

程式碼

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # list to save numbers
        self.number_list = []
        
        # dictionary
        # key: number
        # value: index of number in self.number_list
        self.number_dict = dict()
        
        # size of data structure
        self.size = 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.number_dict:
            return False
        
        else:            
            
            # record new element index in dictionary
            self.number_dict[ val ] = self.size
            
            # append new element into list
            self.number_list.append( val )
            
            # update size of collection
            self.size += 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.number_dict:
            return False
        
        else:

            # To reach O(1) performance, use technique of element swap, and pop on tail
            
            # get the index of element with value
            index_of_val = self.number_dict[val]
            
            
            # update index of last_element
            self.number_dict[ self.number_list[-1] ] = index_of_val
            
            
            # swap val with last element of number_list
            self.number_list[-1], self.number_list[index_of_val] = self.number_list[index_of_val], self.number_list[-1]
            
            
            # remove val from list by popping last
            self.number_list.pop()
            
            # remove val from dictionary by deleting key
            del self.number_dict[val]
        
            # update size of collection
            self.size -= 1
        
            return True
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """

        return random.choice( self.number_list )

複雜度分析

時間複雜度:

insert(), revmoe(), getRandom() 皆為平均O(1)的複雜度。

空間複雜度:

insert(), revmoe(), getRandom() 單獨一次操作也是O(1)。

全體來說，會需要一個O(n)的空間, n值由插入元素的總數量決定。

關鍵知識點

這題還有額外要求getRandom() O(1)的需求，因此用傳統的set()直接來儲存是無法滿足題目條件的。

Reference:

[1] Python by dict and list with swap [w/ Comment]