ผสานลำดับที่เรียงแล้วสองชุด
เดินผ่านลิสต์ทั้งสองด้วยตัวชี้ชุดละหนึ่งตัว
ผสานลำดับที่เรียงแล้วสองชุด เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ขั้นตอนการผสาน
เมื่อกำหนดรายการที่ เรียงลำดับแล้วสองรายการ ให้รวมเป็นรายการเดียวที่เรียงลำดับแล้ว การผสานนี้เป็นหัวใจของการเรียงลำดับแบบผสาน และพบได้ในงานต่าง ๆ มากมาย 🔗
ข้อมูลสองชุด ตัวชี้ชุดละหนึ่งตัว
กำหนด ตัวชี้ให้แต่ละรายการ โดยเริ่มต้นทั้งสองตัวที่ดัชนี 0 จากนั้นเลื่อนตัวชี้ไปข้างหน้าพร้อมกันและไม่ย้อนกลับ
i = 0
j = 0เลือกค่าที่น้อยกว่าเสมอ
ในแต่ละขั้นตอน ให้เปรียบเทียบ สมาชิกหน้าสุดของทั้งสองรายการ แล้วเพิ่มค่าที่น้อยกว่าเข้าไปในผลลัพธ์ เพราะค่านั้นต้องอยู่ถัดไปตามลำดับที่เรียงไว้
เลื่อนตัวชี้ของฝ่ายชนะ
หลังจากเลือกค่าแล้ว ให้ advanceเฉพาะตัวชี้จากรายการที่ให้ค่านั้น ส่วนอีกรายการยังมีสมาชิกที่น้อยที่สุดรออยู่
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1ลูปหลัก
ผสานต่อไป ตราบใดที่ทั้งสองรายการยังมีสมาชิก เมื่อรายการใดรายการหนึ่งหมด การเปรียบเทียบก็ไม่สมเหตุสมผลอีกต่อไป
while i < len(a) and j < len(b):
# compare and append
passเติมค่าที่เหลือ
เมื่อรายการหนึ่งว่างเปล่า อีกรายการก็เรียงลำดับไว้แล้ว ดังนั้นเพียง appendส่วนท้ายที่เหลือของรายการนั้นต่อเข้ากับผลลัพธ์ได้โดยตรง
out.extend(a[i:])
out.extend(b[j:])เหตุผลที่ส่วนท้ายไม่ต้องทำอะไร
ส่วนท้ายที่เหลือเรียงลำดับไว้แล้ว จึงไม่ต้องเปรียบเทียบเพิ่มเติม การเรียกใช้ extend หนึ่งในสองครั้งนั้นจึงไม่เพิ่มอะไรเลย
เวลารวมเชิงเส้น
สมาชิกทุกตัวถูกอ่าน หนึ่งครั้ง ดังนั้นการผสานรายการขนาด n และ m สองรายการจึงใช้เวลา O(n + m) ซึ่งเร็วได้เท่านี้แล้ว
รักษาความคงลำดับ
การใช้ <= เมื่อค่าเท่ากันจะรักษาลำดับเดิมของสมาชิกที่เท่ากันไว้ ความคงลำดับนี้สำคัญเมื่อคุณต้องเก็บข้อมูลเพิ่มเติมไปพร้อมกัน
ผสานโดยย้อนจากด้านหลังได้เช่นกัน
หากต้องผสานลงในบัฟเฟอร์ที่ไม่มีพื้นที่สำรอง ให้เดินจาก ด้านหลังแทน โดยวางค่าที่มากที่สุดไว้ท้ายสุด แนวคิดเหมือนเดิม เพียงกลับด้านกัน
จากการผสานสู่การเรียงลำดับ
แบ่งรายการ เรียงลำดับแต่ละครึ่ง แล้วผสานกลับ นี่คือการเรียกซ้ำของ การเรียงลำดับแบบผสาน การผสานด้วยตัวชี้สองตัวที่คุณเพิ่งเรียนรู้คือกลไกหลักของวิธีนี้
ตรวจสอบอย่างรวดเร็ว
คุณกำลังผสานรายการที่เรียงลำดับแล้วสองรายการ โดยมีตัวชี้ในแต่ละรายการ
สรุปทบทวน
เดินผ่านรายการที่เรียงลำดับแล้วสองรายการด้วย ตัวชี้รายการละหนึ่งตัว โดยเลือกสมาชิกหน้าสุดที่น้อยกว่าเสมอ แล้วเติมส่วนท้ายที่เหลือ วิธีนี้ใช้เวลา O(n + m) และเป็นกลไกสำคัญของการเรียงลำดับแบบผสาน 🚀
คำถามที่พบบ่อย
บทเรียน “ผสานลำดับที่เรียงแล้วสองชุด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ผสานลำดับที่เรียงแล้วสองชุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ 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 ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ตัวชี้สองตัวบนอาร์เรย์ที่เรียงแล้ว
- ค้นหาคู่ที่มีผลรวมกำหนด
- ลบค่าซ้ำในตำแหน่งเดิม
- ผสานลำดับที่เรียงแล้วสองชุด