สมมติว่าเรามีโครงสร้างข้อมูลที่รองรับการดำเนินการต่อไปนี้ทั้งหมดในเวลาเฉลี่ย O(1)
-
insert(val) − สิ่งนี้จะแทรก val รายการไปยังชุดหากยังไม่มีอยู่
-
remove(val) − สิ่งนี้จะลบ val ของไอเท็มออกจากเซ็ตหากมีอยู่
-
getRandom - สิ่งนี้จะส่งคืนองค์ประกอบสุ่มจากชุดองค์ประกอบปัจจุบัน แต่ละองค์ประกอบต้องมีความน่าจะเป็นที่จะถูกส่งกลับเท่ากัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สำหรับการเริ่มต้น ให้กำหนดแผนผังหลักและอาร์เรย์องค์ประกอบ
-
สำหรับฟังก์ชัน insert() จะใช้ val เป็นอินพุต
-
ถ้า val ไม่มีอยู่ใน parent map หรือ parent[val] =0 ให้ใส่ val เข้าไปในองค์ประกอบ แล้วตั้งค่า parent[val] :=1 แล้วคืนค่า true
-
-
คืนค่าเท็จ
-
สำหรับเมธอด remove() จะใช้ val เพื่อลบ
-
ถ้า val ไม่มีอยู่ใน parent map หรือ parent[val] =0 ให้คืนค่าเท็จ
-
ตั้งค่าหลัก[val] :=0
-
index :=ดัชนีของ val ในอาร์เรย์องค์ประกอบ
-
หากดัชนีไม่เท่ากับความยาวขององค์ประกอบ – 1
-
temp :=องค์ประกอบสุดท้ายขององค์ประกอบ
-
ตั้งค่าองค์ประกอบสุดท้ายขององค์ประกอบ :=val
-
ตั้งค่าองค์ประกอบ[ดัชนี] :=อุณหภูมิ
-
-
ลบองค์ประกอบสุดท้ายขององค์ประกอบ
-
เมธอด 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
