LeetCode #268 Missing Number: 5 วิธีเถียงกันว่าใครเร็วสุด แล้วให้ benchmark ตัดสิน

Missing Number #268 เป็นโจทย์ที่ดูง่ายจนน่าสงสัยครับ เขาให้ list ของตัวเลข n ตัวที่ไม่ซ้ำกัน ทุกตัวอยู่ในช่วง 0 ถึง n ซึ่งมีทั้งหมด n + 1 ค่า แปลว่าจะมีอยู่หนึ่งเลขที่หายไป ให้หาเลขนั้น เช่น [3, 0, 1] มี n = 3 ช่วงที่ควรมีคือ 0, 1, 2, 3 ขาด 2 ก็ตอบ 2 บน LeetCode กำหนด n ไม่เกิน 10,000

ข้อนี้น่าสนใจเพราะแก้ได้อย่างน้อย 5 แบบที่คิดคนละมุมจริงๆ ผมเลยลองให้แต่ละวิธีเป็นตัวละครแล้วปล่อยให้เถียงกันเอง จากนั้นค่อยเอาผล benchmark ที่วัดบนเครื่องจริงมาตัดสิน ปิดท้ายด้วยบารอนสรุปให้ครับ

รู้จักผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัย
ลุงถึก มดงานแก่ใส่หมวกนิรภัย ถือแว่นขยาย	ไล่หาทีละเลข (brute force)	ขยันแบบมด เดินตรวจทีละใบไม่ข้ามสักใบ ช้าแต่ซื่อ
ป้าเรียง แม่ไก่ใส่ผ้ากันเปื้อน ถือปึกการ์ด	sort ก่อนแล้วไล่ดู	ชอบเรียงไข่ลงแผงให้เป็นแถว ต้องจัดให้เข้าที่ก่อนทำอะไร
เจ๊จด กระรอกใส่เสื้อกั๊ก ถือสมุดจด	จดลง set แล้วเช็ก	จดไว้หมดว่าซ่อนลูกโอ๊กไว้ตรงไหน ไม่แคร์ว่าจะเปลืองกระดาษ
น้าบวก นกฮูกใส่เสื้อไหมพรม ถือลูกคิด	สูตรผลบวก	ใจเย็น ชอบทางลัดคณิตศาสตร์
น้องซอร์ ปูเสฉวนตัวจิ๋ว สองก้ามชูตลอด	XOR	เด็กแสบ ชอบจับคู่แล้วให้หักล้างกันหายไป
บารอน สิงโตทะเลใส่โค้ทกรมท่า เสื้อคอเต่าสีเทาอมเขียว	กรรมการ	เข้มแต่แฟร์ ฟังตัวเลขมากกว่าเสียงดัง

ตัวละครการ์ตูนหกตัวยืนเรียงกัน จากซ้าย มดงานใส่หมวกนิรภัยถือแว่นขยาย แม่ไก่ถือปึกการ์ด กระรอกถือสมุดจด นกฮูกถือลูกคิด ปูเสฉวนชูก้าม และสิงโตทะเลใส่โค้ทกรมท่ากอดอก

ยกที่ 1: ลุงถึก ไล่หาทีละตัว

มดงานแก่ใส่หมวกนิรภัยก้มส่องการ์ดทีละใบด้วยแว่นขยาย แถวการ์ดยาวสุดลูกหูลูกตา มีรอยเท้าเดินวนกลับไปจุดเริ่มหลายรอบ

ลุงถึก: “ง่ายจะตาย ลุงก็ถามไปทีละเลข มีศูนย์ไหม มีหนึ่งไหม มีสองไหม เจอตัวไหนไม่มีก็จบ ไม่ต้องคิดเยอะ”

ป้าเรียง: “แล้วลุงหาว่า ‘มีไหม’ ยังไงล่ะ”

ลุงถึก: “ก็ไล่ดูทั้งกองไง ทุกรอบเลย”

ป้าเรียง: “นั่นแหละปัญหา ถาม 10,000 เลข แต่ละรอบไล่ดูอีก 10,000 ใบ ลุงจะนั่งถึงเย็นเลยนะ”

ใน Python คำสั่ง x in nums เมื่อ nums เป็น list จะไล่ดูทีละตัวจากต้นจนเจอ (Python wiki บอกว่าเป็น O(n)) พอทำซ้ำ n + 1 รอบ ทั้งหมดจึงเป็น O(n²) แต่ไม่ใช้หน่วยความจำเพิ่ม เทียบง่ายๆ เหมือนเช็กชื่อนักเรียนโดยอ่านรายชื่อทั้งห้องใหม่ทุกครั้งที่เรียกชื่อหนึ่งคน

ข้อดี: อ่านปุ๊บเข้าใจปั๊บ ไม่มีทางผิด เหมาะเอาไว้เทียบคำตอบตอนเขียน test
ข้อเสีย: ช้ามากเมื่อ n ใหญ่ ถ้าตอบแค่วิธีนี้ในห้องสัมภาษณ์ คนสัมภาษณ์จะถามต่อทันที

ยกที่ 2: ป้าเรียง จัดให้เข้าที่ก่อน

แม่ไก่ใส่ผ้ากันเปื้อนเรียงการ์ดเป็นแถวเหมือนเรียงไข่ลงแผง ข้างๆ มีแผงไข่ที่เรียงไว้เรียบร้อย

ป้าเรียง: “ป้าขอเรียงจากน้อยไปมากก่อนนะ พอเรียงแล้ว ช่องที่ 0 ต้องเป็นเลข 0 ช่องที่ 1 ต้องเป็นเลข 1 ช่องไหนเลขไม่ตรงกับเบอร์ช่อง ก็ช่องนั้นแหละที่หาย”

เจ๊จด: “แล้วถ้าไล่จนสุดแล้วตรงหมดล่ะป้า”

ป้าเรียง: “ก็แปลว่าที่หายคือเลขตัวท้ายสุด n ไงจ๊ะ อันนี้ลืมกันบ่อย”

การเรียงใช้เวลา O(n log n) ส่วนไล่เช็กเป็น O(n) ในโค้ดผมใช้ sorted(nums) ซึ่งสร้าง list ใหม่ เลยกินที่ O(n) แต่ไม่ไปแก้ list ต้นฉบับ ถ้ายอมให้แก้ต้นฉบับจะใช้ nums.sort() แทนก็ได้

ข้อดี: คิดง่าย และถ้าข้อมูลเรียงมาให้แล้ว ใช้ binary search ต่อได้เลย
ข้อเสีย: เสียเวลาเรียงของทั้งกองเพื่อหาของชิ้นเดียว

ยกที่ 3: เจ๊จด จดก่อนค่อยเช็ก

กระรอกใส่เสื้อกั๊กจดสมุดอย่างมั่นใจ ข้างหลังมีกองสมุดสูงท่วมหัว สื่อว่าวิธีนี้กินหน่วยความจำ

เจ๊จด: “เจ๊ไม่เรียงหรอก เสียเวลา เจ๊จดทุกเลขลงสมุดก่อนรอบเดียว แล้วค่อยเปิดดูว่าเลขไหนไม่ได้จด เปิดดูแป๊บเดียวก็รู้”

ลุงถึก: “แต่สมุดเจ๊หนาเท่ากองการ์ดเลยนะ”

เจ๊จด: “ก็ใช่ แต่เร็วกว่าลุงหลายร้อยเท่า ยอมเปลืองกระดาษหน่อยแล้วกัน”

set ใน Python เช็กว่ามีค่านั้นไหมได้ใน O(1) โดยเฉลี่ย ทั้งวิธีจึงเป็น O(n) แต่ต้องใช้ที่เพิ่ม O(n) สำหรับ set

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

ยกที่ 4: น้าบวก ใช้สูตรลัด

นกฮูกใส่เสื้อไหมพรมนั่งดีดลูกคิดสบายๆ มีชาร้อนวางข้างตัว แถวการ์ดด้านหลังไม่ต้องแตะเลย

น้าบวก: “ใจเย็นๆ กันก่อน ไม่ต้องเรียง ไม่ต้องจดอะไรเลย ผลรวม 0 ถึง n มีสูตรอยู่แล้ว คือ n คูณ (n + 1) หาร 2 เอาไปลบกับผลรวมของที่มีอยู่จริง ส่วนที่ขาดก็คือเลขที่หาย”

เจ๊จด: “เดี๋ยวนะ แค่นี้เองเหรอ”

น้าบวก: “แค่นี้แหละ เหมือนนับเงินในลิ้นชักแล้วรู้ว่าขาดไปเท่าไหร่ ไม่ต้องรู้ว่าแบงก์ไหนหาย”

บวกทั้ง list รอบเดียวเป็น O(n) และใช้ที่เพิ่ม O(1) ใน Python ตัวเลขไม่มีวัน overflow แต่ถ้าย้ายไปเขียนภาษาที่ใช้ int ขนาดตายตัว เช่น Java หรือ C++ กับ n ที่ใหญ่มากๆ ค่า n * (n + 1) อาจล้นได้ ที่ n ไม่เกิน 10,000 ตามโจทย์ยังไม่ล้น int 32 บิตครับ

ข้อดี: โค้ดสั้นสุด ไม่ใช้หน่วยความจำเพิ่ม
ข้อเสีย: ต้องระวัง overflow ในภาษาอื่น และใช้ได้เพราะโจทย์รับประกันว่าหายแค่ตัวเดียว

ยกที่ 5: น้องซอร์ จับคู่ให้หายไป

ปูเสฉวนตัวจิ๋วถือการ์ดสองใบชนกันจนหายวับ ด้านหลังมีถุงเท้าตากเป็นคู่ เหลือข้างเดียวที่ไม่มีคู่

น้องซอร์: “น้าบวกระวังล้นด้วยนะ หนูไม่ต้องห่วงเรื่องนี้เลย XOR ของเลขตัวเดียวกันสองครั้งได้ศูนย์ หนูเลยเอาเลข 0 ถึง n มา XOR รวมกับทุกเลขใน list ตัวที่มีคู่ก็หักกันหายหมด เหลือตัวเดียวที่ไม่มีคู่ ก็คือตัวที่หายไง”

ลุงถึก: “พูดอะไรของหนู ลุงงง”

น้องซอร์: “เหมือนถุงเท้าลุงไง จับคู่ให้หมดแล้วข้างที่เหลือโดดเดี่ยว แปลว่าอีกข้างหาย”

XOR (^) มีคุณสมบัติ a ^ a = 0, a ^ 0 = a และสลับลำดับได้ เลยเดินรอบเดียว O(n) ใช้ที่ O(1) และไม่มีปัญหาล้นแม้ในภาษาที่ int ขนาดตายตัว

ข้อดี: ไม่ล้น ไม่ใช้ที่เพิ่ม และเป็นท่ามาตรฐานของโจทย์ตระกูล “หาตัวที่ไม่มีคู่”
ข้อเสีย: คนที่ไม่คุ้น XOR อ่านแล้วงง ต้องอธิบายเพิ่มตอนสัมภาษณ์

โค้ดทั้ง 5 วิธีพร้อม test

บล็อกนี้รันจริงตอนตรวจบทความ ทดสอบทุกวิธีกับตัวอย่างโจทย์ กรณีขอบ (หายเลข 0, หายเลขท้ายสุด n, list มีตัวเดียว) เช็กว่าไม่มีวิธีไหนไปแก้ list ต้นฉบับ และสุ่มอีก 200 ชุดให้ทุกวิธีตอบตรงกัน

import random
import unittest


def missing_brute(nums: list[int]) -> int:
    for x in range(len(nums) + 1):
        if x not in nums:
            return x
    raise ValueError("no missing number")


def missing_sort(nums: list[int]) -> int:
    for i, x in enumerate(sorted(nums)):
        if i != x:
            return i
    return len(nums)


def missing_set(nums: list[int]) -> int:
    seen = set(nums)
    for x in range(len(nums) + 1):
        if x not in seen:
            return x
    raise ValueError("no missing number")


def missing_gauss(nums: list[int]) -> int:
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)


def missing_xor(nums: list[int]) -> int:
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result


ALL = [missing_brute, missing_sort, missing_set, missing_gauss, missing_xor]


class TestMissingNumber(unittest.TestCase):
    def check(self, nums: list[int], expected: int) -> None:
        for fn in ALL:
            with self.subTest(fn=fn.__name__, nums=nums[:10]):
                self.assertEqual(fn(list(nums)), expected)

    def test_examples(self) -> None:
        self.check([3, 0, 1], 2)
        self.check([0, 1], 2)
        self.check([9, 6, 4, 2, 3, 5, 7, 0, 1], 8)

    def test_edges(self) -> None:
        self.check([0], 1)
        self.check([1], 0)
        self.check([1, 2, 3], 0)
        self.check([0, 1, 2], 3)

    def test_input_not_modified(self) -> None:
        nums = [2, 0, 3]
        for fn in ALL:
            fn(nums)
        self.assertEqual(nums, [2, 0, 3])

    def test_random_against_each_other(self) -> None:
        rng = random.Random(268)
        for _ in range(200):
            n = rng.randint(1, 60)
            missing = rng.randint(0, n)
            nums = [x for x in range(n + 1) if x != missing]
            rng.shuffle(nums)
            self.check(nums, missing)


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

ใน missing_xor ผมเริ่ม result ที่ n แล้ว XOR i ^ x ไปพร้อมกัน เพราะ enumerate ให้ i แค่ 0 ถึง n - 1 ต้องเติม n เข้าไปเองครับ

benchmark ตัดสิน

มด แม่ไก่ กระรอก นกฮูก และปูเสฉวนเถียงกันวุ่นรอบโต๊ะ สิงโตทะเลใส่โค้ทกรมท่าเดินเข้ามายกมือห้าม

บารอน: “พอ เถียงกันมาพอแล้ว ใครเร็วจริงไม่ต้องพูด ไปวัดมา”

ผมวัดบน box ของบล็อก (Intel Xeon 8 vCPU, Linux, Python 3.14.7) ด้วยโมดูล timeit ใช้ list ที่สลับลำดับแบบสุ่ม (seed 268) วัด 7 รอบแล้วเอาค่า median ต่อการเรียกหนึ่งครั้ง มีสองขนาด คือ n = 10,000 ซึ่งเป็นขนาดใหญ่สุดของโจทย์ กับ n = 1,000,000 ที่ใหญ่เกินโจทย์ไว้ดูว่าพอข้อมูลโตแล้วอันดับเปลี่ยนไหม ลุงถึกวัดแค่ขนาดแรก เพราะเป็น O(n²)

โค้ดด้านล่างเป็นโค้ดบางส่วน ใช้ฟังก์ชันจากบล็อกด้านบน ผมเซฟไว้เป็นไฟล์ solutions.py แล้ว import มาใช้

import random, statistics, timeit
from solutions import ALL

def make(n, seed=268):
    rng = random.Random(seed)
    missing = rng.randint(0, n)
    nums = [x for x in range(n + 1) if x != missing]
    rng.shuffle(nums)
    return nums, missing

for n, fns in [(10_000, ALL), (1_000_000, ALL[1:])]:
    nums, missing = make(n)
    for fn in fns:
        assert fn(nums) == missing
        number = 1 if fn.__name__ == "missing_brute" else (20 if n == 10_000 else 3)
        times = timeit.repeat(lambda: fn(nums), number=number, repeat=7)
        ms = statistics.median(t / number for t in times) * 1000
        print(n, fn.__name__, f"{ms:.3f} ms")

กราฟแท่งสเกล log เวลาต่อการเรียกของทั้ง 5 วิธี ที่ n เท่ากับ 10,000 ลุงถึกใช้ 303.6 ms ป้าเรียง 1.36 ms เจ๊จด 0.354 ms น้าบวก 0.044 ms น้องซอร์ 0.404 ms และที่ n เท่ากับ 1,000,000 ป้าเรียง 301.6 ms เจ๊จด 116.9 ms น้าบวก 12.8 ms น้องซอร์ 96.9 ms

วิธี	`n = 10,000`	`n = 1,000,000`
ลุงถึก (ไล่ทีละตัว)	303.612 ms	ไม่ได้วัด
ป้าเรียง (sort)	1.360 ms	301.632 ms
เจ๊จด (set)	0.354 ms	116.913 ms
น้าบวก (สูตรผลบวก)	0.044 ms	12.815 ms
น้องซอร์ (XOR)	0.404 ms	96.886 ms

ตัวเลขนี้วัดจากเครื่องเดียวครับ เครื่องอื่นหรือ Python เวอร์ชันอื่นจะได้ค่าไม่เท่านี้ แต่สิ่งที่น่าจะเห็นเหมือนกันคือ

ที่ n = 10,000 ลุงถึกช้ากว่าน้าบวกราว 6,900 เท่า (303.612 ÷ 0.044) นี่คือราคาของ O(n²)
น้าบวกชนะทั้งสองขนาด เพราะ sum() ของ Python ทำงานในโค้ด C ทั้งก้อน ส่วนลูป for ของน้องซอร์รันทีละรอบในตัวแปลภาษา Python
น้องซอร์กับเจ๊จดเป็น O(n) เท่ากัน และที่ n = 10,000 ก็เร็วพอๆ กัน (0.404 กับ 0.354 ms) แต่ที่ล้านตัว น้องซอร์แซงเพราะไม่ต้องสร้าง set ขนาดล้านตัว
Big-O บอกว่าโตเร็วแค่ไหน แต่ไม่ได้บอกว่าใครชนะในภาษาไหน ต้องวัดเองถึงจะรู้

น้องซอร์: “เดี๋ยวๆ หนูก็ O(n) เหมือนน้านะ ทำไมที่ล้านตัวหนูช้ากว่าน้าเกือบแปดเท่า”

น้าบวก: “ก็น้าให้ C บวกให้ไง หนูวนลูปเองทุกรอบ”

ลุงถึก: “ลุงขอไม่พูดอะไรละกัน”

บารอนสรุป

สิงโตทะเลใส่โค้ทกรมท่ายืนอธิบายหน้ากระดานกราฟแท่ง มด แม่ไก่ กระรอก ปูเสฉวน และนกฮูกยืนฟัง มดเกาหมวกอย่างเขินๆ

บารอน: “เอาล่ะ ฟังนะ ทุกคนตอบถูกหมด ไม่มีใครผิด แต่ต่างกันที่ราคาที่ต้องจ่าย

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

ถ้าเขียน Python ทั่วไป ใช้น้าบวก สั้นสุดและวัดมาแล้วว่าเร็วสุด แต่ถ้าสัมภาษณ์ด้วย Java หรือ C++ หรือเขาถามเรื่อง overflow ให้ตอบน้องซอร์ แล้วเล่าให้ฟังว่าทำไมไม่ล้น

ในห้องสัมภาษณ์ เริ่มจากลุงถึกให้เห็นว่าเข้าใจโจทย์ แล้วไล่ขึ้นมาทีละขั้น พร้อมบอกเวลากับหน่วยความจำของแต่ละวิธี แค่นี้ก็ได้คะแนนแล้ว จบ”

สรุปเทียบทุกวิธี

วิธี	เวลา	หน่วยความจำเพิ่ม	ใช้เมื่อ
ลุงถึก (ไล่ทีละตัว)	`O(n²)`	`O(1)`	เป็นตัวเทียบคำตอบใน test
ป้าเรียง (sort)	`O(n log n)`	`O(n)` กับ `sorted()`	ข้อมูลเรียงมาแล้ว หรือต้องเรียงอยู่แล้ว
เจ๊จด (set)	`O(n)`	`O(n)`	โจทย์อาจหายหลายตัว
น้าบวก (สูตรผลบวก)	`O(n)`	`O(1)`	Python ทั่วไป เร็วสุดในการวัดครั้งนี้
น้องซอร์ (XOR)	`O(n)`	`O(1)`	ภาษาที่ `int` ล้นได้ หรือโจทย์หาตัวไม่มีคู่

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

ลืมกรณีหายเลขท้ายสุด วิธี sort ต้อง return len(nums) เมื่อไล่ครบแล้วไม่เจอช่องที่เลขไม่ตรง ตัวอย่าง [0, 1] ต้องตอบ 2
ลืมเติม n ในวิธี XOR enumerate ให้เบอร์ช่องแค่ถึง n - 1 ถ้าไม่เริ่ม result ที่ n คำตอบจะเพี้ยน
ใช้ x in nums กับ list ในลูป หน้าตาเหมือนวิธี set แต่จริงๆ คือวิธีของลุงถึก ที่ n = 10,000 ช้ากว่ากันราว 850 เท่า
แก้ list ต้นฉบับโดยไม่ตั้งใจ nums.sort() เปลี่ยน list ของคนเรียก ถ้าไม่แน่ใจให้ใช้ sorted(nums)
เชื่อ Big-O อย่างเดียว สองวิธีที่เป็น O(n) เท่ากันอาจต่างกันหลายเท่าในภาษาจริง ถ้าอยากรู้ต้องวัด

ลองต่อเอง

ลองแก้โจทย์ให้หายสองเลขแทนหนึ่งเลข แล้วดูว่าใครในห้าคนนี้ยังสู้ต่อได้ เจ๊จดต่อยอดได้ทันที น้าบวกต้องใช้สองสมการ ส่วนน้องซอร์ต้องหาทางแยกสองตัวออกจากกัน ข้อนี้สนุกดีครับ