LeetCode 287 Find the Duplicate Number: 4 วิธีจาก Set ถึง Floyd Cycle

โจทย์ Find the Duplicate Number ให้ array ยาว n + 1 ซึ่งทุกค่าอยู่ในช่วง 1..n และมีค่าหนึ่งซ้ำอย่างน้อยสองครั้ง ต้องหาค่าซ้ำโดยไม่แก้ input และใช้หน่วยความจำเพิ่มคงที่สำหรับคำตอบระดับเต็มครับ

เงื่อนไขช่วงค่าคือกุญแจ เพราะทำให้ array มองเป็นกราฟที่ทุก index ชี้ไปยัง index ถัดไปได้ เมื่อมีช่องมากกว่าค่าที่เป็นไปได้หนึ่งช่อง ต้องเกิดวงจรเหมือนบัตรคิวที่มีเลขหนึ่งถูกแจกซ้ำ

วิธีที่ 1: Hash set

เดินค่าแล้วคืนตัวแรกที่เคยเห็น

• เวลา O(n)
• หน่วยความจำ O(n)
• อ่านง่ายที่สุด เหมาะเมื่อ memory ไม่ใช่ข้อจำกัด

วิธีที่ 2: Sort สำเนา

คัดลอก input, sort แล้วหาเพื่อนบ้านที่เท่ากัน

• เวลา O(n log n)
• หน่วยความจำ O(n) เพราะห้ามแก้ input
• เหมาะเมื่ออยาก inspect ลำดับหรือใช้ primitive sort ที่เชื่อถือได้ แต่ไม่ตรงข้อจำกัด memory

วิธีที่ 3: Binary search บนช่วงค่า

เลือกค่ากลาง mid แล้วนับว่ามีกี่สมาชิก <= mid ถ้ามากกว่า mid ค่าซ้ำอยู่ครึ่งล่างตามหลักกล่องนกพิราบ มิฉะนั้นอยู่ครึ่งบน

• เวลา O(n log n) เพราะสแกน array ทุกระดับ
• หน่วยความจำ O(1)
• ไม่แก้ input และไม่พึ่งการตีความเป็น linked list

วิธีที่ 4: Floyd cycle detection

มอง nums[index] เป็น pointer ถัดไป ใช้ตัวเดินช้ากับเร็วหา meeting point แล้วเริ่มตัวหนึ่งจากจุดเริ่มเพื่อหาปากวงจร ค่าที่ปากวงจรคือค่าซ้ำ

• เวลา O(n)
• หน่วยความจำ O(1)
• เร็วสุดตาม constraints แต่ invariant ต้องอธิบายให้เข้าใจ ไม่ใช่ท่องสูตร

import unittest


def find_with_set(nums):
    seen = set()
    for value in nums:
        if value in seen:
            return value
        seen.add(value)
    raise ValueError("no duplicate")


def find_with_value_binary_search(nums):
    low, high = 1, len(nums) - 1
    while low < high:
        middle = (low + high) // 2
        count = sum(value <= middle for value in nums)
        if count > middle:
            high = middle
        else:
            low = middle + 1
    return low


def find_with_floyd(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    finder = nums[0]
    while finder != slow:
        finder = nums[finder]
        slow = nums[slow]
    return finder


class FindDuplicateTests(unittest.TestCase):
    def assert_all_methods(self, nums, expected):
        original = nums.copy()
        self.assertEqual(find_with_set(nums), expected)
        self.assertEqual(find_with_value_binary_search(nums), expected)
        self.assertEqual(find_with_floyd(nums), expected)
        self.assertEqual(nums, original)

    def test_duplicate_twice(self):
        self.assert_all_methods([1, 3, 4, 2, 2], 2)

    def test_duplicate_many_times(self):
        self.assert_all_methods([3, 1, 3, 4, 2, 3], 3)

    def test_smallest_shape(self):
        self.assert_all_methods([1, 1], 1)


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

Decision table

สถานการณ์	Hash set	Sort copy	Value binary search	Floyd
input ใหญ่	เร็วแต่กิน memory	ช้ากว่า	สแกนหลายรอบ	ดีที่สุด
memory จำกัด	ไม่ผ่าน	ไม่ผ่าน	ผ่าน	ผ่าน
readability	ง่ายที่สุด	ง่าย	ปานกลาง	ต้องอธิบายวงจร
input sorted อยู่แล้ว	คืนเพื่อนบ้านซ้ำได้ง่าย	ไม่ต้อง sort	ใช้ได้	ใช้ได้
streaming input	ทำได้ด้วย set	ต้องเก็บทั้งหมด	ต้องสแกนซ้ำ	ต้อง random access
ห้ามแก้ input	ผ่าน	ต้อง copy	ผ่าน	ผ่าน
ค่าไม่อยู่ใน 1..n	set ยังทำงาน	sort ยังทำงาน	invariant พัง	อาจ index พัง

Best default ภายใต้ constraints ของโจทย์: Floyd เพราะได้ทั้ง O(n) และ O(1) โดยไม่แก้ input หากกำลังเขียน production code ที่ข้อมูลอาจผิด contract ให้ validate ก่อน หรือเลือก set เพื่อ fail อย่างควบคุมได้

Edge cases และ trade-offs

• ค่าซ้ำอาจปรากฏมากกว่าสองครั้ง
• ค่าซ้ำอาจอยู่ต้นหรือท้าย array
• input เล็กสุด [1, 1]
• Floyd พึ่งทุกค่าเป็น index ที่ใช้ได้ ถ้าข้อมูลภายนอกไม่ผ่าน validation อาจเกิด IndexError
• binary search บน “ช่วงค่า” ไม่ได้ sort input และไม่ใช่ binary search บนตำแหน่ง

Recap

• set ง่ายและ robust แต่ใช้ O(n) memory
• value binary search ใช้ memory คงที่แต่เวลา O(n log n)
• Floyd แปลง array เป็นวงจรและเป็น best default ตามโจทย์
• contract ช่วง 1..n คือเหตุผลที่วิธี memory คงที่ทำงานได้