Insert Delete GetRandom O(1): Thiết Kế Cấu Trúc Dữ Liệu Hỗ Trợ Toàn Bộ O(1)

Đề bài: Thiết kế cấu trúc dữ liệu hỗ trợ 3 operation trung bình O(1):

• insert(val): Thêm val nếu chưa có. Trả về True/False.
• remove(val): Xóa val nếu có. Trả về True/False.
• getRandom(): Trả về phần tử ngẫu nhiên, mỗi phần tử xác suất như nhau.

Ý tưởng: List + Hash Map

• List vals: lưu giá trị, hỗ trợ getRandom bằng random.choice (O(1)).
• Dict idx: mapping val -> index trong vals, hỗ trợ insert/remove/lookup O(1).
• Xóa O(1): swap phần tử cần xóa với phần tử cuối list, pop cuối, cập nhật index của phần tử swapped.

Code Python

import random

class RandomizedSet:
    def __init__(self):
        self.vals = []      # List values
        self.idx = {}       # val -> index in vals
    
    def insert(self, val: int) -> bool:
        if val in self.idx:
            return False
        self.idx[val] = len(self.vals)
        self.vals.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        if val not in self.idx:
            return False
        
        # Index của val cần xóa
        i = self.idx[val]
        # Phần tử cuối
        last_val = self.vals[-1]
        
        # Swap val với phần tử cuối
        self.vals[i] = last_val
        self.idx[last_val] = i
        
        # Pop cuối
        self.vals.pop()
        del self.idx[val]
        return True
    
    def getRandom(self) -> int:
        return random.choice(self.vals)

# Test
rs = RandomizedSet()
print(rs.insert(1))    # True
print(rs.remove(2))    # False
print(rs.insert(2))    # True
print(rs.getRandom())  # 1 hoặc 2
print(rs.remove(1))    # True
print(rs.insert(2))    # False (đã có)
print(rs.getRandom())  # 2

Phân tích độ phức tạp

• insert: O(1) average (dict + list append)
• remove: O(1) average (swap + pop + dict delete)
• getRandom: O(1) (random.choice trên list)
• Space: O(n)

Lưu ý quan trọng

• Swap với phần tử cuối là key để xóa O(1) mà không dịch chuyển mảng.
• Cập nhật idx[last_val] sau swap.
• random.choice phân bố đều trên list.

Kết luận

Kết hợp List (random access) + HashMap (index lookup) đạt O(1) cho cả 3 operation. Pattern kinh điển cho "RandomizedSet" và các biến thể (RandomizedCollection cho phép duplicate).