Giả sử chúng ta có cấu trúc dữ liệu hỗ trợ tất cả các hoạt động sau trong thời gian trung bình O (1).
-
insert (val) - Thao tác này sẽ Chèn val mục vào tập hợp nếu chưa có.
-
remove (val) - Thao tác này sẽ xóa val một mục khỏi tập hợp nếu nó xuất hiện.
-
getRandom - Điều này sẽ trả về một phần tử ngẫu nhiên từ tập hợp các phần tử hiện tại. Mỗi phần tử phải có cùng xác suất được trả về.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Để khởi tạo, hãy xác định một bản đồ mẹ và mảng các phần tử
-
Đối với hàm insert (), nó sẽ lấy val làm đầu vào
-
nếu val không có trong bản đồ mẹ hoặc cha [val] =0, thì hãy chèn val vào các phần tử và đặt cha [val]:=1 và trả về true
-
-
trả về false
-
Đối với phương thức remove (), sẽ mất val để loại bỏ
-
nếu val không có trong bản đồ mẹ hoặc cha [val] =0, thì trả về false
-
đặt cấp độ gốc [val]:=0
-
index:=chỉ số của val trong mảng phần tử
-
nếu chỉ mục không giống với độ dài của các phần tử - 1
-
temp:=phần tử cuối cùng của các phần tử
-
đặt phần tử cuối cùng của các phần tử:=val
-
đặt phần tử [index]:=temp
-
-
xóa phần tử cuối cùng của các phần tử
-
Phương thức getRandom () sẽ trả về bất kỳ giá trị ngẫu nhiên nào có trong mảng phần tử
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
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()) Đầu vào
Initialize the class, then call the insert(), remove(), getRandom() functions. See the implementation.
Đầu ra
True False True 2 True False 2