LeetCode #48 Rotate Image: ยีราฟ จิ้งจอก เพนกวิน มดงาน หมุนรูป 90 องศาให้ไม่เบี้ยว

โจทย์ Rotate Image #48 ให้ตารางตัวเลข n×n (เหมือนรูปภาพที่แต่ละช่องคือพิกเซล) แล้วสั่งให้หมุนตามเข็มนาฬิกา 90 องศา และกำหนดว่าต้องแก้ตารางเดิม ห้ามจองตารางใหม่ขนาดเท่ากันมาใช้

นี่คือสิ่งที่แอปแกลเลอรีในมือถือทำทุกครั้งที่คุณกดปุ่มหมุนรูปแนวนอนให้เป็นแนวตั้ง แค่ในโจทย์รูปเป็นสี่เหลี่ยมจัตุรัส

ก่อนหมุน        หลังหมุน 90° ตามเข็ม
1 2 3           7 4 1
4 5 6    →      8 5 2
7 8 9           9 6 3
แถวบนสุด (1 2 3) กลายเป็นคอลัมน์ขวาสุด

รอบนี้ให้สัตว์ 4 ตัวสาธิตคนละวิธี แล้ว บารอน สิงโตทะเลใส่โค้ทสรุปจาก benchmark บนเครื่องนี้ครับ

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

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
ยีราฟก๊อปปี้	สร้างตารางใหม่แล้ววางทีละช่อง	คอยาว มองเห็นทั้งตาราง วางใหม่หมด
จิ้งจอกเจ้าเล่ห์	`zip(*matrix[::-1])` ของ Python	ใช้ทริกของภาษาให้ได้ในบรรทัดเดียว
เพนกวินสองจังหวะ	สลับแนวทแยง แล้วกลับแต่ละแถว	เดินเป็นจังหวะ ทีละขั้นชัดๆ
มดงาน	หมุนทีละชั้นแบบ 4 มุมพร้อมกัน	ขยัน ขนทีละ 4 ชิ้นวนรอบขอบ
บารอน	กรรมการ	ดูตัวเลขก่อนตัดสิน

วิธีที่ 1: ยีราฟก๊อปปี้ — ตารางใหม่

ช่อง (i, j) เดิมไปอยู่ที่ (j, n-1-i) ยีราฟสร้างตารางเปล่า วางทุกช่องตามสูตร แล้วค่อยคัดลอกกลับ

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

วิธีที่ 2: จิ้งจอกเจ้าเล่ห์ — zip

จิ้งจอกกลับลำดับแถว (matrix[::-1]) แล้วใช้ zip จับคอลัมน์มาทำเป็นแถว ได้รูปที่หมุนแล้ว: matrix[:] = [list(r) for r in zip(*matrix[::-1])]

เวลา: O(n²)
หน่วยความจำเพิ่ม: O(n²) — สร้างแถวใหม่ทั้งหมดก่อนแทนที่
ข้อดี: สั้นและเร็วใน Python เพราะงานหลักอยู่ในโค้ด C
ข้อเสีย: ไม่ใช่ in-place จริงตามกติกา ผู้สัมภาษณ์มักไม่ให้คะแนนเต็ม และคนที่ไม่รู้จัก * กับ zip อ่านไม่ออก

วิธีที่ 3: เพนกวินสองจังหวะ — transpose แล้วกลับแถว

จังหวะแรก “transpose” คือสลับช่อง (i, j) กับ (j, i) เหมือนพับกระดาษตามเส้นทแยง จังหวะสองคือกลับลำดับในแต่ละแถว

เดิม        transpose     กลับแต่ละแถว
1 2 3       1 4 7         7 4 1
4 5 6   →   2 5 8    →    8 5 2
7 8 9       3 6 9         9 6 3

เวลา: O(n²)
หน่วยความจำเพิ่ม: O(1) — สลับในตารางเดิม
ข้อดี: in-place จริง อธิบายด้วยภาพสองขั้นได้ จำง่าย
ข้อเสีย: แตะแต่ละช่องประมาณ 2 รอบ

วิธีที่ 4: มดงาน — หมุนทีละชั้น

มดมองตารางเป็นวงแหวนซ้อนกันเหมือนหัวหอม ชั้นนอกสุด ชั้นถัดเข้าไป … ในแต่ละชั้น มดหยิบ 4 ช่องที่อยู่ตำแหน่งตรงกันของขอบบน ขวา ล่าง ซ้าย แล้ววนย้ายพร้อมกันทีละชุด

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

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

import unittest

def img_new(m):
    n = len(m); out = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            out[j][n - 1 - i] = m[i][j]
    m[:] = out

def img_zip(m):
    m[:] = [list(r) for r in zip(*m[::-1])]

def img_transpose_reverse(m):
    n = len(m)
    for i in range(n):
        for j in range(i + 1, n):
            m[i][j], m[j][i] = m[j][i], m[i][j]
    for row in m:
        row.reverse()

def img_layers(m):
    n = len(m)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            off = i - first
            top = m[first][i]
            m[first][i] = m[last - off][first]
            m[last - off][first] = m[last][last - off]
            m[last][last - off] = m[i][last]
            m[i][last] = top

ALL = [img_new, img_zip, img_transpose_reverse, img_layers]

class RotateImageTest(unittest.TestCase):
    def check(self, grid, want):
        for f in ALL:
            m = [row[:] for row in grid]; f(m)
            self.assertEqual(m, want, f.__name__)

    def test_3x3(self):
        self.check([[1, 2, 3], [4, 5, 6], [7, 8, 9]],
                   [[7, 4, 1], [8, 5, 2], [9, 6, 3]])

    def test_4x4(self):
        self.check([[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]],
                   [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]])

    def test_1x1(self):
        self.check([[1]], [[1]])

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

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

วัดด้วย timeit บน Python 3.14.7 (x86_64) ตารางสุ่มสองขนาด วัด 5 รอบเอาค่าดีที่สุด

วิธี	100×100 (ms)	500×500 (ms)	ที่เพิ่ม
จิ้งจอก: zip	0.167	4.734	O(n²)
เพนกวิน: transpose + กลับแถว	0.222	7.482	O(1)
มดงาน: ทีละชั้น	0.258	9.225	O(1)
ยีราฟ: ตารางใหม่	0.325	11.352	O(n²)

จิ้งจอกเร็วสุดทั้งสองขนาด เพราะ zip ทำงานในโค้ด C ส่วนในกลุ่มที่ไม่จองที่เพิ่ม เพนกวินเร็วกว่ามด แม้มดจะย้ายแต่ละช่องครั้งเดียว เพราะ row.reverse() ของเพนกวินเป็นงานก้อนเดียวที่ภาษาเร่งให้ ขณะที่มดคำนวณดัชนีเองทุกครั้ง ตัวเลขเป็นของเครื่องนี้เท่านั้น เครื่องคุณจะต่างไป

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

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด (กติกา in-place)	เพนกวิน	วาดภาพ 2 ขั้นได้ ผ่านกติกา โค้ดสั้น
สัมภาษณ์ที่ถามต่อเรื่องย้ายน้อยครั้งสุด	มดงาน	แสดงว่าคิดเป็นชั้นได้ แต่ต้องมีเทสต์
โค้ด Python งานจริง ไม่บังคับ in-place	จิ้งจอก (zip)	เร็วสุดในการวัด
ภาพใหญ่มาก หน่วยความจำตึง	เพนกวิน	ไม่จองตารางที่สอง
ภาษา C / embedded ที่คุมทุกไบต์	มดงาน	ย้ายครั้งเดียวต่อช่อง ไม่มี overhead ของ Python
สอนมือใหม่	ยีราฟ แล้วต่อด้วยเพนกวิน	เห็นสูตรตำแหน่งก่อน แล้วค่อยเห็นทางลดหน่วยความจำ

ค่าเริ่มต้นภายใต้กติกาของโจทย์ (ห้ามจองตารางใหม่): เพนกวิน transpose + กลับแถว

บารอนสรุป

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

Recap

สูตรตำแหน่ง: (i, j) → (j, n-1-i) เมื่อหมุนตามเข็ม 90°
in-place ง่ายสุด: transpose แล้ว row.reverse() ทุกแถว
หมุนทีละชั้นต้องเทสต์ทั้งขนาดคี่ (3×3) และคู่ (4×4)
Python ที่ไม่บังคับ in-place: zip(*m[::-1]) เร็วสุดในการวัดครั้งนี้
ใช้วิธีตารางใหม่เป็นตัวตรวจคำตอบในเทสต์
ลองหมุนทวนเข็มด้วยการสลับลำดับสองจังหวะของเพนกวิน แล้วเขียนเทสต์เอง