LeetCode #75 Sort Colors: Counting เทียบ Dutch National Flag แบบเขียนทับในที่เดิม

Sort Colors ให้เรียง array ที่มีเพียง 0, 1, 2 ในที่เดิม โดยโจทย์ชวนให้ไม่ใช้ sort สำเร็จรูป ประเด็นสัมภาษณ์คือการเลือกความเรียบง่ายของ counting หรือ invariant ของ Dutch National Flag

วิธี 1: Counting สองรอบ

นับจำนวนแต่ละค่า แล้วเขียน 0, 1, 2 กลับลง array เวลา O(n) พื้นที่ O(1) โค้ดตรงและเสี่ยง bug ต่ำ แต่เดินข้อมูลสองรอบ

วิธี 2: Dutch National Flag รอบเดียว

รักษาสามโซน: ก่อน low เป็น 0, หลัง high เป็น 2 และ mid..high ยังไม่ตรวจ ถ้าเจอ 0 สลับซ้าย ถ้าเจอ 2 สลับขวาโดยยังไม่ขยับ mid เพราะค่าที่สลับกลับมายังไม่ถูกตรวจ

วิธี 3: sorted copy

nums[:] = sorted(nums) อ่านง่ายที่สุด แต่ใช้ O(n log n) และพื้นที่ตาม implementation จึงเหมาะเป็น oracle ในเทสต์มากกว่าเฉลยตามข้อกำหนด

from __future__ import annotations

import unittest


def sort_counting(nums: list[int]) -> None:
    counts = [0, 0, 0]
    for value in nums:
        counts[value] += 1
    index = 0
    for value, count in enumerate(counts):
        nums[index:index + count] = [value] * count
        index += count


def sort_dutch_flag(nums: list[int]) -> None:
    low = mid = 0
    high = len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1


def sort_builtin(nums: list[int]) -> None:
    nums[:] = sorted(nums)


class SortColorsTests(unittest.TestCase):
    def test_all_methods_and_edges(self):
        for solve in (sort_counting, sort_dutch_flag, sort_builtin):
            for case in ([2, 0, 2, 1, 1, 0], [], [1], [2, 2, 0]):
                values = list(case)
                solve(values)
                self.assertEqual(values, sorted(case))


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

Decision table

เงื่อนไข	Counting	Dutch flag	Built-in sort
เวลา	O(n)	O(n)	O(n log n)
extra memory	O(1)	O(1)	สูงกว่า
จำนวนรอบ	2	1	ไม่กำหนด
อ่านง่าย	ดีที่สุด	ปานกลาง	สั้นที่สุด
mutation	มี	มี	มีผ่าน slice
streaming	นับได้ แต่ต้องเขียนปลายทางรอบสอง	ไม่เหมาะ	ไม่เหมาะ

Counting เป็น default ที่อธิบายและดูแลง่าย ถ้า requirement ระบุ one pass ค่อยใช้ Dutch flag และเขียน invariant ไว้ข้าง loop

Recap

• ยืนยันว่า input มีเพียง 0, 1, 2
• ตอนสลับเลข 2 อย่าเลื่อน mid ทันที
• เทสต์ array ว่าง ค่าเดียว และทุกค่าเหมือนกัน
• บอกผู้เรียกชัดว่าฟังก์ชัน mutate input