หาตัวเลขซ้ำ (Find Duplicate Number) ใน Python

โจทย์: อาร์เรย์ขนาด n+1 มีค่าอยู่ในช่วง 1..n แน่นอนว่ามีซ้ำอย่างน้อย 1 ตัว (สมมติซ้ำเพียง 1 ค่า) ให้หาค่านั้น

ตัวอย่าง

Input: [3,1,3,4,2]
Output: 3

อัลกอริทึม Floyd's Tortoise and Hare (Cycle Detection)

มองอาร์เรย์เป็น linked list โดย index ชี้ไปที่ค่า (nums[i] → index nums[i]) จะเกิด cycle ที่จุดซ้ำ

1. Phase 1: หาจุดพบกันของ tortoise (ช้า) และ hare (เร็ว)
2. Phase 2: รีเซ็ต pointer หนึ่งตัวไปที่เริ่มต้น เดินทีละขั้นจนพบกันอีกครั้ง → จุดนั้นคือ duplicate

โค้ด

class Solution:
    def findDuplicate(self, nums):
        # Phase 1
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        
        # Phase 2
        ptr = nums[0]
        while ptr != tortoise:
            ptr = nums[ptr]
            tortoise = nums[tortoise]
        return ptr

# ทดสอบ
sol = Solution()
print(sol.findDuplicate([3,1,3,4,2]))  # 3

ข้อดี

• O(n) time, O(1) space
• ไม่ modify อาร์เรย์ต้นฉบับ

สรุป

Cycle detection ใช้แก้ปัญหา duplicate ใน constraints นี้ได้อย่างขลังเกลียว