หมุนลิสต์ใน Python
ในบทเรียนนี้ คุณจะหมุนลิสต์ไปทางขวา k ตำแหน่งด้วยการตัด (slicing)
บทนำ
ปัญหาที่ต้องแก้
การหมุนลิสต์ปรากฏในตารางเวร (ใครถึงคิวต่อไป) บัฟเฟอร์วงกลม เทคนิคกับรูปภาพ และคำถามสัมภาษณ์ การย้ายรายการทีละขั้นใช้ได้แต่ช้า การ slice ทำได้ในขั้นเดียว
ลองนึกภาพแบบนี้
การหมุนลิสต์เหมือนโต๊ะกลมที่ทุกคนขยับไปทางขวาสองที่นั่ง สองคนสุดท้ายเดินอ้อมไปนั่งที่แรก และคนอื่นๆ คงลำดับเดิม การหมุนครบจำนวนที่นั่งไม่เปลี่ยนอะไรเลย
steps %= len(values)🔁 ขยับ 7 ที่ในโต๊ะ 5 ที่นั่งเท่ากับขยับ 2values[-steps:]🚶 สองคนสุดท้ายย้ายไปด้านหน้าvalues[:-steps]🪑 คนอื่นคงลำดับเดิม+🔗 นั่งรวมกัน: [4, 5, 1, 2, 3]การหมุนลิสต์ไปทางขวา k ตำแหน่งย้าย k รายการสุดท้ายไปด้านหน้า โดยคงลำดับของทุกรายการ
ประเด็นสำคัญ
if not values: return []จัดการลิสต์ว่าง ซึ่ง% len(values)จะหารด้วยศูนย์steps %= len(values)ทำให้การหมุนที่มากเกินวนกลับvalues[-steps:]คือส่วนท้ายที่ย้ายไปด้านหน้า:[4, 5]values[:-steps]คือส่วนที่เหลือ:[1, 2, 3]และ+รวมสองชิ้น
ใช้เมื่อไร?
- การผลัดกันแบบ round-robin และตารางเวร
- บัฟเฟอร์วงกลมและหน้าต่างข้อมูลที่เลื่อน
- คำถามสัมภาษณ์เกี่ยวกับการ slice และ modulo
เมื่อไรยังไม่จำเป็น
- หมุนทีละหนึ่งขั้นซ้ำๆ:
collections.deque.rotateทำในที่เดิมได้อย่างมีประสิทธิภาพ - ลิสต์ขนาดใหญ่มากที่หน่วยความจำเพิ่มมีความสำคัญ: วิธีกลับด้านในที่เดิมเลี่ยงการคัดลอก
ดูการทำงาน
คลิกที่ช่องหรือเลื่อนแถบเพื่อเลือก index ลองแทรกหรือลบเพื่อดูว่าทำไมสมาชิกตัวถัดไปทั้งหมดต้องเลื่อน
โค้ดตัวอย่าง
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))
ผลลัพธ์จากการรัน
[4, 5, 1, 2, 3]
อธิบายโค้ด
การหาเศษ steps %= len(values) จัดการกรณีที่จำนวนก้าวมากกว่าความยาวลิสต์ เพราะการหมุนลิสต์ 5 ตัว 7 ครั้งเท่ากับหมุน 2 ครั้ง การตัด values[-steps:] และ values[:-steps] เอาสมาชิก k ตัวสุดท้ายกับส่วนที่เหลือ แล้วต่อกันตามลำดับใหม่ ความซับซ้อนทั้งด้านเวลาและหน่วยความจำคือ O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ลืมกรณีที่ steps เป็นศูนย์
values[-0:] คือทั้งลิสต์ ถ้าไม่มี % ผลลัพธ์จะยาวเป็นสองเท่า
return values[-steps:] + values[:-steps] # steps = 5 gives a list of 10
steps %= len(values)
return values[-steps:] + values[:-steps]
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
โจทย์ทั้งหมด