LeetCode #189 Rotate Array: เต่า ช้าง แมว นกฮูก กระรอก ใครหมุนอาร์เรย์เก่งสุด

โจทย์ Rotate Array #189 ให้ลิสต์ตัวเลข nums กับจำนวน k แล้วสั่งให้ “หมุนไปทางขวา k ช่อง” แบบแก้ลิสต์เดิมเลย เช่น [1,2,3,4,5,6,7] กับ k=3 ต้องกลายเป็น [5,6,7,1,2,3,4] ตัวท้าย 3 ตัววิ่งวนไปอยู่ข้างหน้า

ภาพในหัวง่ายที่สุดคือคิวรอรถตู้ที่ยืนเป็นวงกลม ทุกคนก้าวไปข้างหน้า k ก้าว คนที่ก้าวเลยหัวแถวก็วนกลับมาท้ายแถว ฟังง่าย แต่พอทำในโค้ดจริง มีวิธีให้เลือกหลายแบบ แต่ละแบบจ่าย “เวลา” กับ “หน่วยความจำ” ไม่เท่ากัน

รอบนี้ผมไม่อธิบายเองครับ ให้สัตว์การ์ตูน 5 ตัวมาเถียงกันคนละวิธี แล้วให้ บารอน (สิงโตทะเลใส่โค้ท กรรมการประจำซีรีส์) ตัดสินด้วยตัวเลขที่รันจริงบนเครื่องนี้

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
เต่าขยัน	ขยับทีละ 1 ช่อง ทำซ้ำ k รอบ	ช้าแต่ไม่หลง ทำตามคำสั่งตรงตัว
ช้างขนของ	สร้างอาร์เรย์ใหม่แล้ววางทีละตัว	มีแรงเยอะ ยอมแบกชั้นวางอีกชุด
แมวขี้เกียจ	ใช้ slicing ของ Python	ชอบทางลัดที่ภาษาเตรียมไว้ให้
นกฮูกนักคิด	กลับลำดับ 3 ครั้ง	ไม่ใช้ที่เพิ่ม แต่ต้องเข้าใจเหตุผล
กระรอกโยนลูกนัท	ย้ายเป็นวงจร (cyclic replacement)	โยนของต่อกันเป็นวง ต้องนับดีๆ
บารอน	กรรมการ	ฟังตัวเลข ไม่ฟังเสียงดัง

ก่อนเริ่ม ทุกตัวตกลงกันข้อหนึ่ง: k อาจใหญ่กว่าความยาวลิสต์ได้ หมุน 10 ช่องในลิสต์ยาว 7 ก็เท่ากับหมุน 3 ช่อง เลยต้องทำ k %= n ก่อนเสมอ (% คือเศษจากการหาร)

วิธีที่ 1: เต่าขยัน — ขยับทีละช่อง k รอบ

เต่าเก็บตัวสุดท้ายไว้ในมือ เลื่อนทุกตัวไปทางขวาหนึ่งช่อง แล้ววางตัวที่ถือไว้ที่หัว ทำแบบนี้ k รอบ

• เวลา: O(n·k) — ลิสต์ยาว n ต้องเลื่อน n ตัว ทำ k รอบ
• หน่วยความจำเพิ่ม: O(1) — ถือของแค่ชิ้นเดียว
• ข้อดี: อธิบายง่ายที่สุด เด็กที่เพิ่งเรียน loop เข้าใจทันที
• ข้อเสีย: ถ้า n และ k ใหญ่ ช้ามาก บน LeetCode มักไม่ผ่านเวลา

วิธีที่ 2: ช้างขนของ — อาร์เรย์ใหม่

ช้างสร้างชั้นวางเปล่าขนาดเท่าเดิม แล้วหยิบของช่อง i ไปวางที่ช่อง (i + k) % n เสร็จแล้วค่อยเทกลับลงลิสต์เดิม

• เวลา: O(n) — แตะทุกตัวครั้งเดียว
• หน่วยความจำเพิ่ม: O(n) — ต้องมีชั้นวางอีกชุด
• ข้อดี: สูตรตรงไปตรงมา เขียนผิดยาก เหมาะเวลาสัมภาษณ์ที่อยากได้คำตอบถูกก่อน
• ข้อเสีย: ใช้หน่วยความจำเพิ่มเท่าขนาดข้อมูล

วิธีที่ 3: แมวขี้เกียจ — slicing

แมวบอกว่า “ทำไมต้องเหนื่อย” แล้วเขียนบรรทัดเดียว nums[:] = nums[-k:] + nums[:-k] คือเอา k ตัวท้ายมาต่อหน้า k ตัวแรก ส่วน nums[:] = ทำให้แก้ลิสต์ตัวเดิม ไม่ใช่สร้างชื่อใหม่

• เวลา: O(n) ตามตาราง TimeComplexity ของ Python การ slice และต่อลิสต์ใช้เวลาตามจำนวนสมาชิก
• หน่วยความจำเพิ่ม: O(n) — slice สร้างลิสต์ชั่วคราว
• ข้อดี: สั้นที่สุด และใน Python เร็วมาก เพราะงานหนักไปทำในโค้ด C ของตัวภาษา
• ข้อเสีย: ผู้สัมภาษณ์บางคนจะถามต่อว่า “ถ้าห้ามใช้ที่เพิ่มล่ะ” และต้องระวัง k=0 (nums[-0:] คือทั้งลิสต์ ผลยังถูก แต่คนอ่านงง ผมจึงเช็ก k ก่อน)

วิธีที่ 4: นกฮูกนักคิด — กลับลำดับ 3 ครั้ง

นกฮูกเสนอวิธีที่ดูเหมือนมายากล:

เริ่ม          1 2 3 4 | 5 6 7      (k = 3)
กลับทั้งหมด     7 6 5 | 4 3 2 1
กลับ k ตัวแรก   5 6 7 | 4 3 2 1
กลับส่วนที่เหลือ 5 6 7 | 1 2 3 4   ← คำตอบ

เหตุผลคือ การกลับทั้งหมดพาส่วนท้ายมาไว้หน้าแล้ว แค่ลำดับข้างในกลับหัว จึงกลับแต่ละส่วนอีกครั้งให้ตรง

• เวลา: O(n) — แต่ละตัวถูกสลับประมาณ 2 ครั้ง
• หน่วยความจำเพิ่ม: O(1)
• ข้อดี: คำตอบมาตรฐานเมื่อโจทย์บอกว่า “ทำแบบ in-place” ใช้ได้ทุกภาษา
• ข้อเสีย: ต้องอธิบายเหตุผลให้ได้ ไม่งั้นดูเหมือนท่องจำ

วิธีที่ 5: กระรอกโยนลูกนัท — ย้ายเป็นวงจร

กระรอกหยิบของช่องแรก โยนไปช่อง (i + k) % n เอาของที่อยู่ตรงนั้นมาถือแทน โยนต่อไปเรื่อยๆ จนวนกลับมาที่เดิม ถ้ายังย้ายไม่ครบทุกตัว (เกิดเมื่อ n กับ k มีตัวหารร่วม เช่น n=6, k=2) ก็เริ่มวงใหม่ที่ช่องถัดไป

• เวลา: O(n) — แต่ละตัวถูกย้ายครั้งเดียว
• หน่วยความจำเพิ่ม: O(1)
• ข้อดี: ย้ายน้อยครั้งที่สุดในทางทฤษฎี
• ข้อเสีย: เขียนพลาดง่ายที่สุด โดยเฉพาะเคสวงหลายวง ผมใส่เทสต์ n=6, k=2 ไว้ดักตรงนี้เลย

โค้ดทั้ง 5 วิธี พร้อมเทสต์

โค้ดนี้รันจริงตอนตรวจบทความ ทุกวิธีต้องผ่านเทสต์ชุดเดียวกัน รวมเคส k เท่ากับความยาวลิสต์ และเคสที่วงจรแตกเป็นหลายวง

import unittest

def rot_brute(nums, k):
    n = len(nums); k %= n
    for _ in range(k):
        last = nums[-1]
        for i in range(n - 1, 0, -1):
            nums[i] = nums[i - 1]
        nums[0] = last

def rot_extra(nums, k):
    n = len(nums); out = [0] * n
    for i, x in enumerate(nums):
        out[(i + k) % n] = x
    nums[:] = out

def rot_slice(nums, k):
    k %= len(nums)
    if k:
        nums[:] = nums[-k:] + nums[:-k]

def _rev(a, l, r):
    while l < r:
        a[l], a[r] = a[r], a[l]
        l += 1; r -= 1

def rot_reverse(nums, k):
    n = len(nums); k %= n
    _rev(nums, 0, n - 1); _rev(nums, 0, k - 1); _rev(nums, k, n - 1)

def rot_cyclic(nums, k):
    n = len(nums); k %= n
    moved = start = 0
    while moved < n:
        cur, prev = start, nums[start]
        while True:
            nxt = (cur + k) % n
            nums[nxt], prev = prev, nums[nxt]
            cur = nxt; moved += 1
            if cur == start:
                break
        start += 1

ALL = [rot_brute, rot_extra, rot_slice, rot_reverse, rot_cyclic]

class RotateTest(unittest.TestCase):
    def check(self, data, k, want):
        for f in ALL:
            a = list(data); f(a, k)
            self.assertEqual(a, want, f.__name__)

    def test_examples(self):
        self.check([1, 2, 3, 4, 5, 6, 7], 3, [5, 6, 7, 1, 2, 3, 4])
        self.check([-1, -100, 3, 99], 2, [3, 99, -1, -100])

    def test_k_equals_n_and_bigger(self):
        self.check([1, 2, 3], 3, [1, 2, 3])
        self.check([1, 2, 3], 4, [3, 1, 2])

    def test_multiple_cycles(self):
        self.check([1, 2, 3, 4, 5, 6], 2, [5, 6, 1, 2, 3, 4])

if __name__ == "__main__":
    unittest.main()

Benchmark ที่รันจริง (17 ต.ค. 2026 บนเครื่องนี้)

เครื่องมือวัดคือ timeit ของ Python 3.14.7 บนเครื่อง x86_64 ตัวนี้ วัด 5 รอบแล้วเอาค่าที่ดีที่สุด ลิสต์ยาว 100,000 ตัว หมุน k = 37,123

วิธี	เวลาต่อครั้ง (ms)	ที่เพิ่ม
แมว: slicing	0.925	O(n)
นกฮูก: กลับ 3 ครั้ง	3.470	O(1)
ช้าง: อาร์เรย์ใหม่	3.825	O(n)
กระรอก: วงจร	7.618	O(1)

เต่าช้าเกินกว่าจะวัดที่ขนาดเดียวกัน ผมเลยวัดแยกที่ลิสต์ยาว 2,000 ตัว k = 500: เต่าใช้ 18.796 ms ส่วนนกฮูกที่ขนาดเดียวกันใช้ 0.073 ms ห่างกันราว 250 เท่า

ตัวเลขนี้เป็นของเครื่องนี้และ Python รุ่นนี้เท่านั้น เครื่องคุณจะต่างไป แต่ลำดับเร็ว-ช้ามักคล้ายกัน สิ่งที่น่าสังเกตคือ กระรอกที่ “ย้ายน้อยครั้งสุด” ตามทฤษฎีกลับช้าสุดในกลุ่ม O(n) เพราะใน Python การคำนวณ % และสลับค่าทีละตัวใน loop มีต้นทุนต่อรอบสูง ส่วนแมวชนะเพราะ slicing ทำงานในโค้ด C ทั้งก้อน

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด ห้ามใช้ที่เพิ่ม	นกฮูก (กลับ 3 ครั้ง)	O(n) เวลา O(1) ที่ อธิบายเหตุผลได้ชัด
สัมภาษณ์ อยากได้คำตอบถูกเร็ว	ช้าง (อาร์เรย์ใหม่)	สูตรเดียว เขียนผิดยาก แล้วค่อยปรับเป็นนกฮูก
โค้ด Python ใช้งานจริง (hot path)	แมว (slicing)	เร็วสุดในการวัด อ่านง่าย ถ้ารับ O(n) ชั่วคราวได้
หน่วยความจำจำกัดมาก (เช่น บอร์ดเล็ก ภาษา C)	นกฮูก หรือ กระรอก	ไม่จองที่เพิ่ม นกฮูกเขียนง่ายกว่า
สอนมือใหม่	เต่า แล้วต่อด้วยช้าง	เห็นภาพการเลื่อนก่อน แล้วค่อยเห็นว่าทำไมต้องเร็วขึ้น

ค่าเริ่มต้นที่ผมแนะนำภายใต้เงื่อนไขของโจทย์ (แก้ in-place): นกฮูก ถ้าเขียนภาษาที่ไม่มี slicing เร็วๆ; ถ้าเป็น Python ในงานจริง slicing ก็พอ

บารอนสรุป

บารอนกระแอมแล้วบอกว่า “ทุกตัวได้คำตอบถูก แต่จ่ายไม่เท่ากัน เต่าจ่ายด้วยเวลา ช้างกับแมวจ่ายด้วยหน่วยความจำ นกฮูกกับกระรอกจ่ายด้วยความคิด” ในห้องสัมภาษณ์ให้เปิดด้วยช้าง แล้วอัปเกรดเป็นนกฮูกพร้อมวาดภาพกลับลำดับ 3 ขั้นให้ดู ส่วนในงาน Python จริง อย่าอายที่จะใช้แมว เพราะตัวเลขบนเครื่องนี้บอกว่าเร็วที่สุด

Recap

• เริ่มทุกวิธีด้วย k %= n กัน k ใหญ่กว่าลิสต์
• จำ 3 ขั้นของนกฮูก: กลับทั้งหมด → กลับ k ตัวแรก → กลับส่วนที่เหลือ
• ถ้าใช้วิธีวงจร ต้องมีเทสต์เคส n กับ k มีตัวหารร่วม (เช่น 6 กับ 2)
• สัมภาษณ์: เปิดด้วยอาร์เรย์ใหม่ แล้วเสนอ in-place
• Python งานจริง: nums[:] = nums[-k:] + nums[:-k] เร็วสุดในการวัดครั้งนี้ (0.925 ms ที่ 100,000 ตัว)
• ลองรันโค้ดเทสต์ด้านบนบนเครื่องตัวเองแล้วจดเวลาเทียบ