287. Find the Duplicate Number

원문: https://doljae.tistory.com/70

[Find the Duplicate Number - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com](https://leetcode.com/problems/find-the-duplicate-number/)

1. 선형 탐색 (시간 초과)

class Solution:
    def findDuplicate(self, nums):
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                return nums[i]

2. HashMap or Set (공간 초과)

class Solution:
    def findDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)

3. Floyd 순환 알고리즘 (2 pointer, Runner)

from typing import *

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        pointer1 = pointer2 = 0
        while True:
            pointer1 = nums[pointer1]
            pointer2 = nums[pointer2]
            pointer2 = nums[pointer2]
            if pointer1 == pointer2:
                break
        pointer1 = 0
        while pointer1 != pointer2:
            pointer1 = nums[pointer1]
            pointer2 = nums[pointer2]
        return pointer1