ข้อ 10 · LC283 Move Zeroes 🟢

ให้ array (ลิสต์) ตัวเลข nums จงย้ายเลข 0 ทุกตัวไปอยู่ท้ายแถว โดยมีเงื่อนไขสองข้อ: ตัวที่ไม่ใช่ 0 ต้องยังเรียงตามลำดับเดิม และต้องแก้ลงในแถวเดิม ห้ามสร้างแถวใหม่มาแทน

พื้นฐานที่ต้องมีก่อน 4 อย่าง

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

พื้นฐานที่ 1 — in-place หมายถึงอะไร (และห้ามพลาดตรงนี้ใน Python)

in-place แปลว่าแก้ข้อมูลในที่เดิม ไม่สร้างที่เก็บใหม่ที่โตตามขนาดข้อมูล จุดที่ต้องเข้าใจให้ชัด: การมีตัวแปรเพิ่มไม่กี่ตัว (เช่นตัวนับ ตัวชี้ตำแหน่ง) ยังนับว่า in-place อยู่ เพราะจำนวนตัวแปรไม่โตตามความยาวแถว ที่ห้ามคือการสร้าง list ใหม่ทั้งก้อน

และมีกับดักของ Python ที่ทำให้โค้ดดูเหมือนทำงานแต่จริง ๆ ไม่มีอะไรเปลี่ยนเลย

def wrong(nums):
    nums = [x for x in nums if x != 0] + [0] * nums.count(0)   # สร้างลิสต์ใหม่แล้วตั้งชื่อทับ


def right(nums):
    kept = [x for x in nums if x != 0]
    nums[:] = kept + [0] * (len(nums) - len(kept))             # เขียนทับ "ข้างใน" ลิสต์เดิม


a = [0, 1, 0, 3, 12]
wrong(a)
print("หลังเรียก wrong :", a, "<- ไม่มีอะไรเปลี่ยนเลย")

b = [0, 1, 0, 3, 12]
right(b)
print("หลังเรียก right :", b, "<- เปลี่ยนจริง")

หลังเรียก wrong : [0, 1, 0, 3, 12] <- ไม่มีอะไรเปลี่ยนเลย
หลังเรียก right : [1, 3, 12, 0, 0] <- เปลี่ยนจริง

เหตุผล: บรรทัด nums = ... ไม่ได้แก้ลิสต์ มันแค่เอาชื่อ nums ไปแปะกับลิสต์ก้อนใหม่ ส่วนลิสต์เดิมของคนที่เรียกฟังก์ชันยังอยู่เหมือนเดิมไม่ถูกแตะเลย ตรงข้ามกับ nums[:] = ... ที่สั่งว่า "เอาของชุดนี้ไปเขียนทับทุกช่องของลิสต์เดิม" ซึ่งแก้ก้อนเดิมจริง

พื้นฐานที่ 2 — ทำไมห้ามใช้ pop(0) หรือ remove(0)

ความคิดแรกของเกือบทุกคนคือ "เจอ 0 ก็ลบทิ้ง แล้วไปต่อท้ายใหม่" ฟังดูตรงไปตรงมาที่สุด แต่วิธีนี้ช้ามากด้วยเหตุผลที่มองไม่เห็นจากโค้ด: การลบของกลางลิสต์ ต้องเลื่อนของที่อยู่ข้างหลังมันทั้งหมด มาข้างหน้าหนึ่งช่อง

nums = [10, 20, 30, 40, 50]
print("ก่อน :", nums)
nums.pop(0)                      # เอาช่องแรกออก
print("หลัง pop(0) :", nums, "<- ทุกตัวเลื่อนซ้าย 1 ช่อง และลิสต์สั้นลง")

# นับว่าการเลื่อนเกิดขึ้นกี่ครั้งจริง ๆ ถ้าลบ 0 ทีละตัวแบบนี้
def count_shifts(n_zeros, n_total):
    shifts = 0
    length = n_total
    for _ in range(n_zeros):
        shifts += length - 1     # ลบหนึ่งตัว = เลื่อนของที่เหลือทั้งหมด
        length -= 1
    return shifts

print("แถวยาว 100 มี 0 อยู่ 50 ตัว -> เลื่อนของทั้งหมด", count_shifts(50, 100), "ครั้ง")
print("แถวยาว 1000 มี 0 อยู่ 500 ตัว -> เลื่อน", count_shifts(500, 1000), "ครั้ง")
print("สังเกต: แถวยาวขึ้น 10 เท่า แต่งานเพิ่มขึ้นประมาณ 100 เท่า")

ก่อน : [10, 20, 30, 40, 50]
หลัง pop(0) : [20, 30, 40, 50] <- ทุกตัวเลื่อนซ้าย 1 ช่อง และลิสต์สั้นลง
แถวยาว 100 มี 0 อยู่ 50 ตัว -> เลื่อนของทั้งหมด 3725 ครั้ง
แถวยาว 1000 มี 0 อยู่ 500 ตัว -> เลื่อน 374750 ครั้ง
สังเกต: แถวยาวขึ้น 10 เท่า แต่งานเพิ่มขึ้นประมาณ 100 เท่า

บรรทัดสุดท้ายคือหัวใจ: งานโตเป็นกำลังสองของความยาวแถว ไม่ใช่โตตามความยาวแถวตรง ๆ (เขียนย่อว่า O(n²)) นอกจากนี้ pop(0) ยังทำให้ลิสต์สั้นลง ซึ่งขัดกับโจทย์ที่ต้องการให้จำนวนช่องเท่าเดิม และ remove(0) แย่กว่าอีกขั้นเพราะต้องไล่หาตำแหน่งของ 0 ก่อนแล้วจึงเลื่อน

พื้นฐานที่ 3 — การสลับค่าสองตัวในบรรทัดเดียว

Python สลับค่าตัวแปรได้ในบรรทัดเดียวด้วย a, b = b, a เหตุผลที่ทำได้คือ Python คำนวณ ฝั่งขวาให้เสร็จทั้งหมดก่อน (ได้เป็นคู่ค่า) แล้วจึงค่อยจ่ายไปให้ฝั่งซ้าย จึงไม่ต้องมีตัวแปรพักเหมือนภาษาอื่น

a, b = 10, 20
print("ก่อน  : a =", a, ", b =", b)
a, b = b, a                     # Python คำนวณฝั่งขวาให้เสร็จก่อน แล้วค่อยจ่ายให้ฝั่งซ้าย
print("หลัง  : a =", a, ", b =", b)

print("--- ถ้าแยกเป็นสองบรรทัดจะพัง")
x, y = 10, 20
x = y                           # x กลายเป็น 20 ทับค่า 10 ทิ้งไปแล้ว
y = x                           # y ได้ 20 กลับมา ไม่ใช่ 10
print("x =", x, ", y =", y, "<- ค่า 10 หายไปเลย ไม่ได้สลับ")

ก่อน  : a = 10 , b = 20
หลัง  : a = 20 , b = 10
--- ถ้าแยกเป็นสองบรรทัดจะพัง
x = 20 , y = 20 <- ค่า 10 หายไปเลย ไม่ได้สลับ

เรื่องนี้ใช้กับช่องใน array ได้เหมือนกัน คือ nums[i], nums[j] = nums[j], nums[i] และเราจะใช้มันในเฉลยของข้อนี้

พื้นฐานที่ 4 — เช็ค != 0 ไม่ใช่ > 0

constraint บอกว่าค่าในแถวติดลบได้ ถ้าเผลอเขียนเงื่อนไขว่า "มากกว่า 0" เลขติดลบจะถูกเหมาโดนดันไปท้ายเหมือนเป็น 0 ด้วย ซึ่งเป็นบั๊กที่ตัวอย่างในโจทย์จับไม่ได้เพราะตัวอย่างไม่มีเลขติดลบเลย

def wrong_gt(nums):
    insert = 0
    for i in range(len(nums)):
        if nums[i] > 0:            # ผิด: เลขติดลบถูกมองว่าเป็นศูนย์
            nums[insert], nums[i] = nums[i], nums[insert]
            insert += 1
    return nums


def right_ne(nums):
    insert = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[insert], nums[i] = nums[i], nums[insert]
            insert += 1
    return nums


print("แบบ > 0  :", wrong_gt([-1, 0, -2, 3]), "<- เลขติดลบถูกดันไปท้าย และ 0 ค้างกลางแถว")
print("แบบ != 0 :", right_ne([-1, 0, -2, 3]), "<- ถูกต้อง")

แบบ > 0  : [3, 0, -2, -1] <- เลขติดลบถูกดันไปท้าย และ 0 ค้างกลางแถว
แบบ != 0 : [-1, -2, 3, 0] <- ถูกต้อง

ลองแบบตรงไปตรงมาก่อน: สร้างแถวใหม่

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

def build_new(nums):
    kept = [x for x in nums if x != 0]          # เก็บตัวที่ไม่ใช่ 0 ตามลำดับเดิม
    zeros = len(nums) - len(kept)
    return kept + [0] * zeros                   # ต่อท้ายด้วย 0 ให้ครบ

print(build_new([0, 1, 0, 3, 12]))   # [1, 3, 12, 0, 0]

แต่วิธีนี้ผิดกติกาข้อ in-place เพราะลิสต์ kept โตตามจำนวนข้อมูล ถ้าแถวยาวหนึ่งหมื่น kept ก็อาจยาวหนึ่งหมื่นตาม เราจึงต้องหาวิธีทำงานเดียวกันนี้โดยไม่สร้างที่เก็บใหม่ ทั้งหน้าที่เหลือคือการไล่จากวิธีนี้ไปหาวิธีที่ไม่กินพื้นที่เพิ่ม

ความคิดที่ดูถูกแต่ผิด: เจอ 0 แล้วเลื่อนของหลังมาข้างหน้า

นี่คือความคิดที่คนคิดออกเป็นอันดับสองและเป็นกับดักที่ลึกที่สุดของข้อนี้ ไอเดียคือ "เจอ 0 ที่ช่องไหน ก็เลื่อนของที่อยู่หลังมันมาทับ แล้วเอา 0 ไปวางท้ายสุด" ฟังดูสมเหตุสมผลทุกคำ และมันจะ ผ่านตัวอย่างที่ 1 ของโจทย์ ด้วย ทำให้คนเชื่อว่าถูกแล้ว

def shift_left(nums):
    """ความคิดตรงไปตรงมา: เจอ 0 ที่ไหน ก็เลื่อนของหลังมันมาข้างหน้า แล้วยัด 0 ไว้ท้าย"""
    for i in range(len(nums)):
        if nums[i] == 0:
            for j in range(i, len(nums) - 1):
                nums[j] = nums[j + 1]      # เลื่อนของหลังมาทับ
            nums[-1] = 0                   # เอา 0 ไปไว้ท้ายสุด
    return nums


print(shift_left([0, 1, 0, 3, 12]), "<- เคสนี้ดูเหมือนถูก")
print(shift_left([0, 0, 1]), "<- ควรได้ [1, 0, 0]  แต่ได้ผิด!")
print(shift_left([0, 0, 0, 1]), "<- ควรได้ [1, 0, 0, 0]")

[1, 3, 12, 0, 0] <- เคสนี้ดูเหมือนถูก
[0, 1, 0] <- ควรได้ [1, 0, 0]  แต่ได้ผิด!
[0, 1, 0, 0] <- ควรได้ [1, 0, 0, 0]

สาเหตุที่พัง: เมื่อเลื่อนของมาทับช่องที่ i แล้ว ช่องที่ i อาจกลายเป็น 0 ตัวใหม่ (เพราะตัวที่เลื่อนมาเป็น 0) แต่ลูป for พาเราไปช่อง i+1 แล้ว จึงข้าม 0 ตัวนั้นไปเลยไม่มีวันย้อนกลับมาดู เคส [0,0,1] จึงเหลือ 0 ค้างอยู่หน้าแถว

แล้วถ้าแก้ด้วยการเขียน i -= 1 เพื่อให้ย้อนกลับมาดูช่องเดิมอีกครั้ง จะเจอปัญหาใหม่คือ for loop ของ Python จะไม่สนใจการแก้ค่า i ข้างในลูปเลย (เรื่องนี้อธิบายไว้แล้วในหน้า "เลือก for หรือ while ให้ถูก" ของคอร์สพื้นฐาน) และถ้าเปลี่ยนไปใช้ while แล้วเขียน i -= 1 จริง โปรแกรมจะวนไม่จบเพราะ i เด้งไปกลับที่เดิมตลอด

จุดที่ควรสังเกตอีกอย่าง: วิธีเลื่อนนี้ต้องเลื่อนของทั้งแถวทุกครั้งที่เจอ 0 ซึ่งคือปัญหาความช้าเดียวกับ pop(0) ในพื้นฐานที่ 2 เป๊ะ ๆ นั่นเป็นสัญญาณว่าเรากำลังคิดผิดทิศ ทางที่ถูกต้องไม่ควรมีการเลื่อนของทั้งแถวเลย

แนวคิดหลัก: อย่าไปขยับ 0

นี่คือประโยคเดียวที่พลิกข้อนี้จากยากเป็นง่าย: เลิกคิดเรื่องย้าย 0 ไปท้าย ให้คิดแค่ว่า เอาตัวที่ไม่ใช่ 0 ไปเรียงชิดซ้ายให้หมด แล้ว 0 จะไปกองท้ายเองโดยที่เราไม่ต้องสั่งเลย

เปรียบเทียบกับการจัดชั้นหนังสือที่มีช่องว่างแทรกอยู่: เราไม่ต้องเก็บช่องว่างไปไว้ทางขวา เราแค่เลื่อนหนังสือทุกเล่มไปชิดซ้ายเท่าที่ชิดได้ ช่องว่างจะไปรวมกันอยู่ทางขวาเองเป็นผลพลอยได้

แปลเป็นโค้ดต้องมีตัวแปรสองตัวคนละหน้าที่ ตรงนี้คือจุดที่คนติดกันมากที่สุด เพราะเคยชินกับการมี index ตัวเดียวในลูป

ทางที่ 1 — เขียนทับ แล้วเติม 0 (สองรอบ)

ทางแรกทำตรงตามแนวคิดเลย: รอบแรกเอาตัวที่ไม่ใช่ 0 เขียนทับลงช่องต้น ๆ ตามลำดับ รอบสองช่องที่เหลือเติม 0 ให้ครบ ลองรันดูโดยให้มันพิมพ์สภาพแถวหลังจบรอบแรกให้เห็น

nums = [0, 1, 0, 3, 12]
insert = 0

print("รอบที่ 1 — ดันตัวที่ไม่ใช่ศูนย์มาชิดซ้าย")
for x in nums:
    if x != 0:
        nums[insert] = x
        insert += 1
        print("   จด", x, "ลงช่อง", insert - 1, "-> nums =", nums)

print("สภาพแถวหลังจบรอบที่ 1 :", nums, " <- ท้ายแถวเป็นขยะ (3, 12 ค้างอยู่)")
print("จำนวนตัวที่ไม่ใช่ศูนย์ =", insert)

print("รอบที่ 2 — ช่องที่เหลือเติม 0")
for j in range(insert, len(nums)):
    nums[j] = 0
print("ผลลัพธ์สุดท้าย :", nums)

รอบที่ 1 — ดันตัวที่ไม่ใช่ศูนย์มาชิดซ้าย
   จด 1 ลงช่อง 0 -> nums = [1, 1, 0, 3, 12]
   จด 3 ลงช่อง 1 -> nums = [1, 3, 0, 3, 12]
   จด 12 ลงช่อง 2 -> nums = [1, 3, 12, 3, 12]
สภาพแถวหลังจบรอบที่ 1 : [1, 3, 12, 3, 12]  <- ท้ายแถวเป็นขยะ (3, 12 ค้างอยู่)
จำนวนตัวที่ไม่ใช่ศูนย์ = 3
รอบที่ 2 — ช่องที่เหลือเติม 0
ผลลัพธ์สุดท้าย : [1, 3, 12, 0, 0]

บรรทัด [1, 3, 12, 3, 12] คือสิ่งที่ต้องเห็นให้ได้ คนที่ไม่เคยเห็นสภาพนี้แล้วไปลอง print กลางลูปเองจะคิดว่าโค้ดพัง เพราะเลข 3 กับ 12 โผล่สองที่ ความจริงคือของเดิมที่ยังไม่ถูกทับ ซึ่งเป็นเรื่องปกติของการแก้ในที่เดิม รอบที่สองจะไปกลบมันด้วย 0 ทีหลัง

และคำถามที่ควรสงสัยตรงนี้คือ: บรรทัด nums[insert] = x เขียนทับข้อมูลที่ยังกวาดไม่จบ มันจะไปทับตัวที่ยังไม่ได้อ่านไหม คำตอบอยู่ในหัวข้อถัดไป

ทางที่ 2 — สลับที่ (รอบเดียว) และเหตุผลว่าทำไมปลอดภัย

ทางที่สองรวมสองรอบให้เป็นรอบเดียว โดยเปลี่ยนจาก "เขียนทับ" เป็น "สลับที่" ข้อดีคือไม่มีขยะค้างท้ายแถว เพราะการสลับไม่ทำให้ของหายไปไหน มันแค่ย้ายที่ — 0 ที่ถูกเตะออกจากช่องหน้าก็ไปโผล่ที่ช่องหลังพอดี เท่ากับได้การเติม 0 ท้ายแถวมาฟรี ๆ

ตลอดการทำงาน แถวถูกแบ่งเป็น 3 โซนแบบนี้เสมอ:

  [ 1 , 3 | 0 , 0 | 12 , ... ]
    ↑        ↑       ↑
    0        insert  i

  ช่วง [0, insert)   = ตัวไม่ใช่ 0 ที่จัดเรียบร้อยแล้ว เรียงตามลำดับเดิม
  ช่วง [insert, i)   = กอง 0 ที่รอโดนเตะไปท้าย
  ช่วง [i, จบ)       = ส่วนที่ยังไม่ได้อ่าน

ข้อความสามบรรทัดนั้นเป็นจริง ก่อนเริ่มทุกรอบ และยังเป็นจริง หลังจบทุกรอบ ข้อความที่จริงเสมอแบบนี้เรียกว่า invariant (ข้อเท็จจริงคงที่) และมันคือเครื่องมือมาตรฐานที่ใช้พิสูจน์ว่าลูปทำงานถูก

ทำไมการสลับหนึ่งครั้งไม่ทำลาย invariant นี้: ตอนที่เจอ nums[i] ที่ไม่ใช่ 0 ช่องที่ตำแหน่ง insert ต้องเป็น 0 อยู่แล้วแน่นอน เพราะมันอยู่ในโซนกลางซึ่งเป็น 0 ล้วนตามบรรทัดที่สอง การสลับจึงเท่ากับเอา "0 ตัวหน้าสุดของโซนกลาง" ไปแลกกับ "ตัวไม่ใช่ 0 ตัวใหม่" พอดี ผลคือโซนซ้ายได้สมาชิกเพิ่มต่อท้าย และโซนกลางยังเป็น 0 ล้วนเหมือนเดิม ไม่มีตัวไหนหายและไม่มีลำดับไหนสลับ

ส่วนคำถามของทางที่ 1 ว่า "เขียนทับแล้วข้อมูลหายไหม" ก็ตอบด้วยข้อเท็จจริงเดียวกัน: insert ไม่เคยแซง i เพราะ insert ขยับเฉพาะตอนที่ i เจอตัวไม่ใช่ 0 ซึ่งเท่ากับ i ขยับไปแล้วอย่างน้อยเท่ากัน ดังนั้นช่องที่เราเขียนลงไปเป็นช่องที่ i อ่านผ่านไปแล้วเสมอ ไม่มีข้อมูลที่ยังต้องใช้หายไปเลย

และเหตุผลที่ลำดับเดิมไม่เพี้ยน: เราเอาตัวไม่ใช่ 0 ต่อท้าย โซนซ้ายเสมอ ตามลำดับที่ i เดินเจอ ซึ่ง i เดินจากซ้ายไปขวาไม่ย้อน ตัวที่อยู่ซ้ายกว่าในแถวเดิมจึงถูกจัดเข้าโซนซ้ายก่อนเสมอ

ไล่ทีละสเต็ปด้วยมือ (dry run)

ไล่ nums = [0, 1, 0, 3, 12] แบบสลับที่ ให้ดูคอลัมน์สุดท้ายเป็นหลัก เพราะมันคือ invariant ที่เพิ่งพิสูจน์ไป

สามอย่างที่ควรอ่านออกจากตารางนี้: หนึ่ง โซนกลางเป็น 0 ล้วนทุกแถวไม่มีข้อยกเว้น สอง 1, 3, 12 เข้าโซนซ้ายตามลำดับที่เจอ จึงคงลำดับเดิม สาม insert จบที่ 3 ซึ่งเท่ากับจำนวนตัวที่ไม่ใช่ 0 พอดี — เราไม่เคยสั่งย้าย 0 เลยแม้แต่ครั้งเดียว มันไปกองท้ายเองจากการถูกสลับออกไปทีละตัว

กับดักที่คนพลาดบ่อยที่สุด

กับดักที่ 1 — ใช้ตัวชี้หัวกับท้ายเดินเข้าหากัน

คนที่เพิ่งอ่านหน้าแนวคิด Two Pointers มาแล้วมักหยิบแบบ opposite ends มาใช้ทันที คือเจอ 0 ที่หน้าก็เอาตัวท้ายมาถม วิธีนี้เร็วกว่าและเขียนของน้อยกว่าด้วย แต่มันทำลายลำดับเดิม ซึ่งโจทย์ห้ามไว้

def opposite_ends(nums):
    """เอาตัวท้ายมาถมช่องที่เป็น 0 — เร็ว แต่ทำลายลำดับเดิม"""
    left, n = 0, len(nums)
    while left < n:
        if nums[left] == 0:
            n -= 1
            nums[left], nums[n] = nums[n], nums[left]
        else:
            left += 1
    return nums


print(opposite_ends([0, 1, 0, 3, 12]), "<- ควรได้ [1, 3, 12, 0, 0]")
print("ตัวที่ไม่ใช่ศูนย์เรียงผิดลำดับเดิมไปแล้ว")

[12, 1, 3, 0, 0] <- ควรได้ [1, 3, 12, 0, 0]
ตัวที่ไม่ใช่ศูนย์เรียงผิดลำดับเดิมไปแล้ว

บทเรียนที่ควรเก็บไป: ท่านี้ไม่ได้ผิดเสมอไป มันเป็นคำตอบที่ดีที่สุดสำหรับโจทย์ที่ ไม่สนลำดับ (เช่น LC27 Remove Element) เพราะเขียนลงแถวน้อยครั้งกว่ามาก การเลือกท่าจึงขึ้นกับว่าโจทย์บังคับเรื่องลำดับหรือเปล่า ไม่ใช่ว่าท่าไหนดีกว่าท่าไหนโดยตัวมันเอง

กับดักที่ 2 — ลืมรอบที่สอง

ถ้าเลือกทางที่ 1 (เขียนทับ) แล้วลืมลูปเติม 0 คำตอบจะเป็น [1, 3, 12, 3, 12] คือมีขยะค้างท้ายแถว บั๊กนี้หาง่ายถ้าเคยเห็นสภาพระหว่างทางมาก่อน ซึ่งเป็นเหตุผลที่หน้านี้ยกมันมาโชว์ตั้งแต่ต้น

กับดักที่ 3 — สับสนกับโจทย์พี่น้อง

ข้อ 26 Remove Duplicates from Sorted Array ใช้โครงเดียวกันแต่ความหมายของตัวเขียนต่างกันหนึ่งช่อง: ที่ข้อนี้ insert หมายถึง "ช่องว่างถัดไปที่จะวาง" แต่ที่ LC26 ตัวเขียนหมายถึง "ช่องของตัวที่เก็บล่าสุด" คนที่ทำข้อนี้ได้แล้วไปทำ LC26 ต่อจึงมักพลาดเรื่อง off-by-one จำไว้ว่าต้องถามตัวเองทุกครั้งว่าตัวเขียน "ชี้ช่องว่าง" หรือ "ชี้ตัวล่าสุด"

ลองเองก่อน 10–15 นาที

def move_zeroes(nums: list[int]) -> None:
    """แก้ nums ในที่เดิม ไม่ต้อง return อะไร"""
    # เขียนโค้ดของคุณที่นี่
    pass


cases = [
    ([0, 1, 0, 3, 12], [1, 3, 12, 0, 0]),
    ([0], [0]),
    ([1, 2, 3], [1, 2, 3]),
    ([0, 0, 0], [0, 0, 0]),
    ([0, 0, 1], [1, 0, 0]),
    ([-1, 0, -2, 3], [-1, -2, 3, 0]),
]
for nums, expected in cases:
    got = nums[:]
    move_zeroes(got)
    print(got == expected, got)

insert = 0                          # ช่องว่างถัดไปที่จะวางตัวไม่ใช่ 0
for i in range(len(nums)):          # i ไล่อ่านทุกช่อง
    if ______________:              # (1) nums[i] น่าเก็บไหม
        ______________              # (2) เอา nums[i] ไปไว้ช่อง insert
        insert += 1                 # โซนจัดแล้วโตขึ้นหนึ่งช่อง

# ช่อง (2) ทำได้สองแบบ เลือกอันไหนก็ได้:
#   แบบสลับ     : nums[insert], nums[i] = nums[i], nums[insert]   (จบในรอบเดียว)
#   แบบเขียนทับ : nums[insert] = nums[i]   แล้วต้องมีลูปเติม 0 ต่อท้ายอีกรอบ

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        insert = 0                          # (1) slow — ช่องว่างถัดไปของตัวที่ไม่ใช่ 0
        for i in range(len(nums)):          # (2) fast — ไล่ดูทุกช่อง
            if nums[i] != 0:                # (3) เจอตัวที่ต้องเก็บ
                nums[insert], nums[i] = nums[i], nums[insert]   # (4) สลับขึ้นมาข้างหน้า
                insert += 1                 # (5) โซนที่จัดแล้วโตขึ้นหนึ่งช่อง

ตอบ challenge ของโจทย์: เขียนลงแถวให้น้อยที่สุด

โจทย์แถมมาว่า "ทำให้จำนวนครั้งที่เขียนลง array น้อยที่สุด" คำถามนี้ตอบด้วยความรู้สึกไม่ได้ ต้องนับจริง มาสามแบบเทียบกัน: สลับทุกครั้ง, สลับแต่ข้ามตอน i == insert, และเขียนทับสองรอบ

def writes_swap(nums):
    w = insert = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[insert], nums[i] = nums[i], nums[insert]
            w += 2                      # สลับหนึ่งครั้ง = เขียน 2 ช่อง
            insert += 1
    return w


def writes_swap_skip(nums):
    w = insert = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            if i != insert:             # ข้ามการสลับตัวเองกับตัวเอง
                nums[insert], nums[i] = nums[i], nums[insert]
                w += 2
            insert += 1
    return w


def writes_overwrite(nums):
    w = insert = 0
    for x in nums:
        if x != 0:
            nums[insert] = x
            w += 1
            insert += 1
    for j in range(insert, len(nums)):
        nums[j] = 0
        w += 1
    return w


cases = [
    ("0 เยอะ   [0,0,0,0,1]", [0, 0, 0, 0, 1]),
    ("0 น้อย   [1,2,3,4,0]", [1, 2, 3, 4, 0]),
    ("ไม่มี 0  [1,2,3,4,5]", [1, 2, 3, 4, 5]),
]
print("เคส                    | สลับ | สลับ+ข้าม | เขียนทับ")
for name, base in cases:
    print(f"{name} | {writes_swap(base[:]):4} | {writes_swap_skip(base[:]):9} | {writes_overwrite(base[:]):8}")

เคส                    | สลับ | สลับ+ข้าม | เขียนทับ
0 เยอะ   [0,0,0,0,1] |    2 |         2 |        5
0 น้อย   [1,2,3,4,0] |    8 |         0 |        5
ไม่มี 0  [1,2,3,4,5] |   10 |         0 |        5

อ่านตารางแล้วจะเห็นว่าแบบสลับล้วน แพ้ แบบเขียนทับในสองเคสหลัง (8 กับ 10 เทียบกับ 5) เพราะมันเสีย 2 ครั้งต่อหนึ่งตัวไม่ใช่ 0 แม้ในตอนที่สลับตัวเองกับตัวเองซึ่งไม่ได้ย้ายอะไรจริงเลย ส่วนแบบเขียนทับเสียคงที่เท่ากับความยาวแถว เพราะไล่เขียนทุกช่อง

คำตอบของ challenge คือแบบกลาง: เติม if i != insert เข้าไปบรรทัดเดียว เพื่อ ข้ามการสลับที่ไม่ได้ย้ายอะไร ผลคือได้ 0 ครั้งในเคสที่แถวเป็นคำตอบอยู่แล้ว (ถูกต้อง เพราะไม่ต้องแก้อะไรเลย) และไม่เคยแย่กว่าอีกสองแบบในเคสไหน

ทริคและคำถามต่อยอดที่มักถูกถาม

💻 แบบฝึกหัด

ระดับ 1 — ทำตามที่เรียนมา

1. เขียน move_zeroes แบบเขียนทับสองรอบ ให้ผ่านเคสทั้งหมดในเช็คลิสต์ใบ้ขั้น 3
2. เขียนแบบสลับที่รอบเดียว แล้วเทียบผลกับข้อ 1 ว่าตรงกันทุกเคส
3. เติม if i != insert ลงในแบบสลับ แล้วนับจำนวนครั้งที่เขียนด้วยตัวแปร w เทียบกับตารางในหน้านี้

ระดับ 2 — ดัดแปลงโจทย์

1. เขียนฟังก์ชันดัน 0 ไปไว้ หน้า แถว โดยยังคงลำดับเดิมของตัวที่ไม่ใช่ 0
2. เขียน LC27 Remove Element: ให้ค่า val มา ให้ลบทุกตัวที่เท่ากับ val แล้ว return ความยาวใหม่ (ไม่สนลำดับของส่วนที่เหลือ) ลองทำสองแบบคือ slow/fast และ opposite ends แล้วนับจำนวนครั้งที่เขียนเทียบกัน
3. เขียนฟังก์ชันที่ดันตัวที่ หารด้วย 3 ลงตัว ไปท้ายแถว โดยคงลำดับเดิม — ข้อนี้ต้องเปลี่ยนแค่บรรทัดเดียวจากเฉลย

ระดับ 3 — ท้าทาย

1. เขียน LC26 Remove Duplicates from Sorted Array แล้วอธิบายเป็นข้อความว่าตัวเขียนของข้อนั้นหมายถึงอะไร ต่างจาก insert ของข้อนี้อย่างไร
2. เขียนโค้ดสุ่มทดสอบ: สุ่มแถวขึ้นมา 2000 ชุด เทียบผลของเฉลยกับวิธีสร้างแถวใหม่ (ซึ่งถูกแน่นอน) ว่าตรงกันทุกชุด
3. เขียน LC75 Sort Colors (มีแค่ค่า 0, 1, 2) ด้วยการกวาดรอบเดียวและใช้สามตัวชี้ แล้วเขียน invariant ของสี่โซนออกมาเป็นข้อความ