LeetCode 풀기 - 287. Find the Duplicate Number

287. Find the Duplicate Number

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

Find the Duplicate Number - LeetCode

문제)

솔루션1) 정렬

정렬한 다음에 순차적으로 중복된 숫자를 찾습니다.

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

솔루션2) index

방문 했던 index에 -를 곱하게되면 두 번 방문한 index는 양수가 되므로 이를 이용해서 중복 숫자를 찾습니다.

class Solution:
    def findDuplicate(self, nums):
        for i in range(len(nums)):
            idx = abs(nums[i]) - 1
            nums[idx] *= -1
            if nums[idx] > 0:        
                return abs(nums[i])

솔루션3) Floyd's cycle detection 알고리즘

플로이드 순환 알고리즘(Floyd's Tortoise & Hare)을 통해서 해당 문제를 해결할 수 있습니다.

class Solution:
    def findDuplicate(self, nums):
        slow = 0
        fast = 0
        while True:
            # one step
            slow = nums[slow]
            # two step
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow2 = 0
        while True:
            # move one step both
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                break
        return slow

 

함께 보면 좋은 글:

2022.03.03 - [알고리즘/알고리즘 Basic] - [파이썬] Floyd's Cycle Detection 알고리즘

[파이썬] Floyd's Cycle Detection 알고리즘