287. Find the Duplicate Number

[zeikar]

Problem link

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

Problem Summary

배열에서 중복된 수를 찾는 문제. 단 배열의 조작은 불가능하고, 공간복잡도는 O(1)이어야 한다.

Solution

제약 조건이 없다면 매우 쉬운 문제... 하지만 제약 조건과 follow up을 전부 만족하려면 특별한 알고리즘이 필요하다.

일단 해당 문제를 링크드 리스트로 볼 수 있는데 nums의 값을 인덱스로 해서 다음 리스트로 넘어가는 링크드 리스트로 가정하면 링크드 리스트의 사이클을 찾는 문제가 된다.

그리고 사이클을 시간 O(n), 공간 O(1)로 찾는 알고리즘이 바로 Floyd's Tortoise and Hare (Cycle Detection) algorithm 이다.

토끼와 거북이로 투 포인터를 도는 것인데

1. 토끼는 거북이의 2배 속도로 이동하고 토끼와 거북이가 만난다면 사이클이 있는 것이다.
2. 거북이를 시작 지점에 놓고 토끼를 거북이와 같은 속도로 다시 돌게 되면 만나는 포인트가 사이클의 시작 지점이 된다.

그림으로 보면 이해가 좀 쉬워진다.
위 그림에서 토끼는 더 빨리 움직여서 거북이를 따라 잡아야 하므로 y 지점에서 만난다고 할 때

C = y + z
토끼: x + C * n + y
거북이: x + C * m + y

2 * ( x + C * m + y) = x + C * n + y

n, m은 토끼와 거북이가 사이클을 돈 횟수이고 C는 사이클의 길이이다.

위 식을 x에 대해 정리해보면

2x + 2Cm + 2y = x + Cn + y
x = Cn - 2Cm - y
x = Cn - 2Cm - y - z + z
x = Cn - 2Cm - C + z
x = (n - 2m - 1) C + z

여기서 사이클은 절대 좌표로 봤을 때 제자리이므로 제거할 수 있다 (사이클이므로 한바퀴 돌면 그대로 돌아온다) . 그러면

x = z

즉 거북이가 시작점에서 x만큼 이동하는 동안 토끼가 z만큼 이동하게 되면 결국 x 지점에서 만나게 된다.

(증명 참고 및 출처: https://leetcode.com/problems/find-the-duplicate-number/solutions/650942/proof-of-floyd-s-cycle-detection-algorithm-find-the-duplicate-number)

Source Code

from typing import List


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

        return hare