Giả sử chúng ta muốn triển khai cấu trúc dữ liệu tập hợp với các phương thức sau -
- Hàm tạo để tạo một phiên bản mới của một tập hợp
- thêm (val) để chèn số nguyên val vào tập hợp
- tồn tại (val) để kiểm tra xem val có trong tập hợp hay không
- remove (val) để xóa val khỏi tập hợp
Vì vậy, nếu chúng ta xây dựng một tập hợp s, thì hãy gọi s.add (10), s.add (20), s.add (10), s.exists (10), s.remove (10), s.exists ( 10), s.exists (20), thì đầu ra sẽ là
- đối với s.add (10), nó sẽ chèn 10
- đối với s.add (20), nó sẽ chèn 20
- 10 đã sẵn sàng, vì vậy sẽ không có gì xảy ra
- s.exists (10) sẽ trả về true khi ở đó là 10
- Xóa 10 bởi s.remove (10)
- s.exists (10) sẽ trả về false vì 10 bị xóa và một phần tử chỉ có thể ở đó một lần
- s.exists (20) sẽ trả về true khi có 20 ở đó.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định hàm tạo.
- bucket:=một bản đồ trống và bản đồ này sẽ chứa một danh sách dữ liệu
- Xác định một hàm add (). Điều này sẽ mất giá trị
- nếu tồn tại (val) là sai, thì
- chèn val vào cuối nhóm [val]
- Xác định một hàm tồn tại (). Điều này sẽ mất giá trị
- trả về true khi val nằm trong bucket [val], ngược lại là false
- Xác định một hàm remove (). Điều này sẽ mất giá trị
- xóa nhóm [val]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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