LeetCode 常數時間插入、删除和擷取随機元素 python3

設計一個支援在平均 時間複雜度 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();
           

一：按dict來儲存即可在常數時間存取，然後随機傳回dict的鍵值即可

轉載

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}
        

    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
        else:
            self.data[val] = 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 in self.data:
            self.data.pop(val)
            return True
        else:
            return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return random.choice(list(self.data.keys()))


# 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()

           

方法二:

轉載

哈希表 + 動态數組

必須在常數時間擷取到要删除元素的索引，是以需要一個哈希表來存儲值到索引的映射。

綜上所述，我們使用以下資料結構：

• 動态數組存儲元素值
• 哈希表存儲存儲值到索引的映射

remove的過程:

在哈希表中查找要删除元素的索引。

将要删除元素與最後一個元素交換。

删除最後一個元素。

更新哈希表中的對應關系。

from random import choice
class RandomizedSet():
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dict = {}
        self.list = []

        
    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.dict:
            return False
        self.dict[val] = len(self.list)
        self.list.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.dict:
            # move the last element to the place idx of the element to delete
            last_element, idx = self.list[-1], self.dict[val]
            self.list[idx], self.dict[last_element] = last_element, idx
            # delete the last element
            self.list.pop()
            del self.dict[val]
            return True
        return False

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