287. Find the Duplicate Number

Find the Duplicate Number - LeetCode

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