資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中插入、刪除和獲取隨機數 O(1) 操作
假設我們有一個數據結構，它支援以下所有操作，平均時間複雜度為 O(1)。
insert(val) - 如果該值不存在，則將專案 val 插入到集合中。
remove(val) - 如果存在，則從集合中刪除專案 val。
getRandom - 從當前元素集中返回一個隨機元素。每個元素被返回的機率必須相同。
為了解決這個問題，我們將遵循以下步驟 -
初始化時，定義一個父對映和元素陣列。
對於 insert() 函式，它將接收 val 作為輸入。
如果 val 不存在於父對映中，或 parent[val] = 0，則將 val 插入到元素中，並將 parent[val] 設定為 1，並返回 true。
返回 false。
對於 remove() 方法，它將接收要刪除的 val。
如果 val 不存在於父對映中，或 parent[val] = 0，則返回 false。
將 parent[val] 設定為 0。
index := val 在元素陣列中的索引。
如果 index 不等於元素長度減 1。
temp := 元素的最後一個元素。
將元素的最後一個元素設定為 val。
將 elements[index] 設定為 temp。
刪除元素的最後一個元素。
getRandom() 方法將返回元素陣列中存在的任何隨機值。
示例（Python）
讓我們看看以下實現，以便更好地理解 -
import random
class RandomizedSet(object):
def __init__(self):
self.present = {}
self.elements = []
def insert(self, val):
if val not in self.present or self.present[val] == 0:
self.elements.append(val)
self.present[val] = 1
return True
return False
def remove(self, val):
if val not in self.present or self.present[val] == 0:
return False
self.present[val] = 0
index = self.elements.index(val)
if index!=len(self.elements)-1:
temp = self.elements[-1]
self.elements[-1] = val
self.elements[index]=temp
self.elements.pop()
return True
def getRandom(self):
return random.choice(self.elements)
ob = RandomizedSet()
print(ob.insert(1))
print(ob.remove(2))
print(ob.insert(2))
print(ob.getRandom())
print(ob.remove(1))
print(ob.insert(2))
print(ob.getRandom())輸入
Initialize the class, then call the insert(), remove(), getRandom() functions. See the implementation.
輸出
True False True 2 True False 2
更新於: 2020年4月29日
473 次檢視
廣告