อัลกอริทึม Python

หมุนลิสต์ใน Python

ในบทเรียนนี้ คุณจะหมุนลิสต์ไปทางขวา k ตำแหน่งด้วยการตัด (slicing)

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

การหมุนลิสต์ปรากฏในตารางเวร (ใครถึงคิวต่อไป) บัฟเฟอร์วงกลม เทคนิคกับรูปภาพ และคำถามสัมภาษณ์ การย้ายรายการทีละขั้นใช้ได้แต่ช้า การ slice ทำได้ในขั้นเดียว

ลองนึกภาพแบบนี้

การหมุนลิสต์เหมือนโต๊ะกลมที่ทุกคนขยับไปทางขวาสองที่นั่ง สองคนสุดท้ายเดินอ้อมไปนั่งที่แรก และคนอื่นๆ คงลำดับเดิม การหมุนครบจำนวนที่นั่งไม่เปลี่ยนอะไรเลย

จากโต๊ะกลมสู่โค้ด
steps %= len(values)🔁 ขยับ 7 ที่ในโต๊ะ 5 ที่นั่งเท่ากับขยับ 2
values[-steps:]🚶 สองคนสุดท้ายย้ายไปด้านหน้า
values[:-steps]🪑 คนอื่นคงลำดับเดิม
+🔗 นั่งรวมกัน: [4, 5, 1, 2, 3]
ตัดลิสต์เป็นสองชิ้นแล้วสลับกัน
สรุปในประโยคเดียว

การหมุนลิสต์ไปทางขวา k ตำแหน่งย้าย k รายการสุดท้ายไปด้านหน้า โดยคงลำดับของทุกรายการ

ประเด็นสำคัญ

  1. if not values: return [] จัดการลิสต์ว่าง ซึ่ง % len(values) จะหารด้วยศูนย์
  2. steps %= len(values) ทำให้การหมุนที่มากเกินวนกลับ
  3. values[-steps:] คือส่วนท้ายที่ย้ายไปด้านหน้า: [4, 5]
  4. values[:-steps] คือส่วนที่เหลือ: [1, 2, 3] และ + รวมสองชิ้น

ใช้เมื่อไร?

  • การผลัดกันแบบ round-robin และตารางเวร
  • บัฟเฟอร์วงกลมและหน้าต่างข้อมูลที่เลื่อน
  • คำถามสัมภาษณ์เกี่ยวกับการ slice และ modulo

เมื่อไรยังไม่จำเป็น

  • หมุนทีละหนึ่งขั้นซ้ำๆ: collections.deque.rotate ทำในที่เดิมได้อย่างมีประสิทธิภาพ
  • ลิสต์ขนาดใหญ่มากที่หน่วยความจำเพิ่มมีความสำคัญ: วิธีกลับด้านในที่เดิมเลี่ยงการคัดลอก

ดูการทำงาน

คลิกที่ช่องหรือเลื่อนแถบเพื่อเลือก index ลองแทรกหรือลบเพื่อดูว่าทำไมสมาชิกตัวถัดไปทั้งหมดต้องเลื่อน

โค้ดตัวอย่าง

รันโค้ด →
main.py
def rotate_right(values, steps):
    if not values:
        return []
    steps %= len(values)
    return values[-steps:] + values[:-steps]

print(rotate_right([1, 2, 3, 4, 5], 2))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

[4, 5, 1, 2, 3]

อธิบายโค้ด

การหาเศษ steps %= len(values) จัดการกรณีที่จำนวนก้าวมากกว่าความยาวลิสต์ เพราะการหมุนลิสต์ 5 ตัว 7 ครั้งเท่ากับหมุน 2 ครั้ง การตัด values[-steps:] และ values[:-steps] เอาสมาชิก k ตัวสุดท้ายกับส่วนที่เหลือ แล้วต่อกันตามลำดับใหม่ ความซับซ้อนทั้งด้านเวลาและหน่วยความจำคือ O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

ลืมกรณีที่ steps เป็นศูนย์

values[-0:] คือทั้งลิสต์ ถ้าไม่มี % ผลลัพธ์จะยาวเป็นสองเท่า

ปัญหา
return values[-steps:] + values[:-steps]  # steps = 5 gives a list of 10
วิธีแก้
steps %= len(values)
return values[-steps:] + values[:-steps]

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด