สมมติว่าเราต้องการใช้โครงสร้างข้อมูลชุดด้วยวิธีต่อไปนี้ -
- ตัวสร้างเพื่อสร้างอินสแตนซ์ใหม่ของชุด
- add(val) เพื่อแทรกค่าจำนวนเต็มเข้าไปในเซต
- exists(val) เพื่อตรวจสอบว่า val อยู่ในเซตหรือไม่
- remove(val) เพื่อลบ val ออกจากเซ็ต
ดังนั้น หากเราสร้างเซต s ให้เรียก s.add(10), s.add(20), s.add(10), s.exists(10), s.remove(10), s.exists( 10), s.exists(20) จากนั้นผลลัพธ์จะเป็น
- สำหรับ s.add(10) จะแทรก 10
- สำหรับ s.add(20) จะแทรก 20
- 10 อยู่ใน s แล้ว ไม่มีอะไรเกิดขึ้น
- s.exists(10) จะคืนค่าเป็นจริงเมื่อมี 10
- ลบ 10 โดย s.remove(10)
- s.exists(10) จะคืนค่าเท็จเพราะลบ 10 รายการและองค์ประกอบหนึ่งจะมีได้เพียงครั้งเดียว
- s.exists(20) จะคืนค่าเป็นจริงเมื่อมี 20 อยู่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดคอนสตรัคเตอร์
- buckets :=แผนที่ว่างและจะเก็บรายการข้อมูล
- กำหนดฟังก์ชัน add() นี่จะใช้เวลา val
- ถ้ามีอยู่(val) จะเป็นเท็จ ดังนั้น
- ใส่ val ที่ส่วนท้ายของ buckets[val]
- กำหนดฟังก์ชั่นที่มีอยู่() นี่จะใช้เวลา val
- คืนค่า จริง เมื่อ val อยู่ในบัคเก็ต[val] มิฉะนั้น เท็จ
- กำหนดฟังก์ชัน remove() นี่จะใช้เวลา val
- ลบที่เก็บข้อมูล[val]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
s = MySet() s.add(10) s.add(20) s.add(10) s.exists(10) s.remove(10) s.exists(10) s.exists(20)
ผลลัพธ์
True False True
