Chương trình định nghĩa cấu trúc dữ liệu Set không dùng thư viện Python

Triển khai cấu trúc dữ liệu Set với các phương thức:

• Constructor: khởi tạo set rỗng
• add(val): thêm số nguyên val
• exists(val): kiểm tra có trong set không
• remove(val): xóa val khỏi set

Ví dụ: add(10), add(20), add(10), exists(10)→True, remove(10), exists(10)→False, exists(20)→True.

Giải thuật (Dictionary ánh xạ giá trị → list)

1. buckets: defaultdict(list), key là giá trị, value là list chứa giá trị (để kiểm tra tồn tại O(1))
2. add(val): nếu chưa tồn tại → append vào buckets[val]
3. exists(val): trả về
4. remove(val): xóa buckets[val]

Ví dụ triển khai

from collections import defaultdict

class MySet:
    def __init__(self):
        self.buckets = defaultdict(list)
    
    def add(self, val):
        if not self.exists(val):
            self.buckets[val].append(val)
    
    def exists(self, val):
        return val in self.buckets[val]
    
    def remove(self, val):
        del self.buckets[val]

s = MySet()
s.add(10)
s.add(20)
s.add(10)
print(s.exists(10))
s.remove(10)
print(s.exists(10))
print(s.exists(20))

Đầu vào

s = MySet(); s.add(10); s.add(20); s.add(10); s.exists(10); s.remove(10); s.exists(10); s.exists(20)

Đầu ra

True False True