จัดกลุ่มและแบ่งถังด้วยแมป
จัดกลุ่มแอนะแกรมและรายการที่คล้ายกัน
จัดกลุ่มและแบ่งถังด้วยแมป เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
การจัดกลุ่มคือรูปแบบหนึ่ง
โจทย์จำนวนมากขอให้จัดกลุ่มรายการที่มีบางอย่างร่วมกัน การทำแผนที่จากคีย์ไปยังบักเก็ตทำให้เรื่องนี้จบได้ในการไล่ผ่านอย่างเป็นระเบียบเพียงครั้งเดียว 🗂️
เลือกคีย์สำหรับจัดกลุ่ม
เคล็ดลับทั้งหมดอยู่ที่การเลือก คีย์ ที่เหมือนกันสำหรับรายการในกลุ่มเดียวกัน หากเลือกถูก ส่วนที่เหลือก็ง่าย
จัดรายการลงบักเก็ตด้วยพจนานุกรมค่าเริ่มต้น
ใช้ พจนานุกรมค่าเริ่มต้น(รายการ) เพื่อให้คีย์ใหม่ทุกคีย์เริ่มต้นด้วยบักเก็ตว่าง เพิ่มรายการต่อท้ายโดยไม่ต้องตรวจสอบว่าคีย์มีอยู่หรือไม่
from collections import defaultdict
buckets = defaultdict(list)ลูปหลัก
สำหรับแต่ละรายการ ให้คำนวณคีย์ของรายการนั้น แล้ว append รายการลงในบักเก็ตของคีย์นั้น หนึ่งบรรทัดต่อหนึ่งองค์ประกอบก็จัดกลุ่มทุกอย่างได้
for word in words:
buckets[key_of(word)].append(word)จัดกลุ่มแอนนาแกรม
แอนนาแกรมมีตัวอักษรที่เรียงลำดับแล้วเหมือนกัน ดังนั้นสตริงที่เรียงลำดับแล้วจึงเป็นคีย์จัดกลุ่มที่เหมาะที่สุด เรียงลำดับครั้งเดียว แล้วจัดลงบักเก็ตตามค่านั้น
k = ''.join(sorted(word))
buckets[k].append(word)ใช้คีย์ทูเพิลสำหรับจำนวน
เมื่อการเรียงลำดับช้า ทูเพิลของจำนวนตัวอักษรก็ใช้เป็นคีย์ได้เช่นกัน ทูเพิลแฮชได้ จึงนำไปใช้ในพจนานุกรมได้อย่างราบรื่น
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')จัดลงบักเก็ตตามคุณสมบัติ
จัดกลุ่มตัวเลขตาม เศษที่เหลือ ความเป็นคู่หรือคี่ หรือความยาวได้ เพียงเปลี่ยนคีย์ รูปแบบนี้ยังคงเหมือนเดิมในโจทย์ต่าง ๆ
for n in nums:
buckets[n % 3].append(n)แนวคิดการเรียงลำดับแบบบักเก็ต
เมื่อค่าอยู่ในช่วงเล็ก ๆ ให้นำแต่ละค่าใส่บักเก็ตที่มีดัชนี แล้วอ่านค่าตามลำดับ นี่คือการเรียงลำดับที่เกือบเป็นเชิงเส้น
for x in nums:
bucket[x].append(x)รวบรวมผลลัพธ์
หลังจัดลงบักเก็ตแล้ว คำตอบมักอยู่ใน values ของพจนานุกรม แปลงเป็นรายการเมื่อผู้ตรวจต้องการกลุ่มต่าง ๆ โดยตรง
result = list(buckets.values())นับแยกตามกลุ่ม
หากต้องการเพียง ขนาดกลุ่ม ให้จัดลงบักเก็ตในตัวนับหรือรวมความยาวเมื่อจบ เลือกวิธีตามสิ่งที่โจทย์ถามจริง ๆ
sizes = {k: len(v) for k, v in buckets.items()}เหตุใดการทำแผนที่จึงเหนือกว่า
การจัดกลุ่มด้วยแผนที่ใช้ O(n) แทนการเปรียบเทียบทุกคู่ คีย์ที่ผ่านการแฮชช่วยจับคู่ให้เอง
ตรวจสอบอย่างรวดเร็ว
ต้องการจัดกลุ่มคำเพื่อให้แอนนาแกรมอยู่ในบักเก็ตเดียวกัน
สรุป
จัดกลุ่มโดยทำแผนที่ คีย์ ของแต่ละรายการลงในบักเก็ตของพจนานุกรมค่าเริ่มต้น ด้วยการไล่ผ่าน O(n) เพียงครั้งเดียว เลือกคีย์ให้ดี แล้วโจทย์การจัดกลุ่มจะง่ายขึ้นมาก 🚀
คำถามที่พบบ่อย
บทเรียน “จัดกลุ่มและแบ่งถังด้วยแมป” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “จัดกลุ่มและแบ่งถังด้วยแมป” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “จัดกลุ่มและแบ่งถังด้วยแมป”
จัดกลุ่มแอนะแกรมและรายการที่คล้ายกัน คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “จัดกลุ่มและแบ่งถังด้วยแมป” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- เซตสำหรับตรวจสมาชิกและกำจัดค่าซ้ำ
- ดิกชันนารีในฐานะตารางค้นหา
- การใช้งาน Counter และ defaultdict
- จัดกลุ่มและแบ่งถังด้วยแมป