솔루션 개발:

질문

이 기사에서는 Leetcode의 '287. Find the Duplicate Number' 질문을 다룰 것입니다. Google 없이는 일정한 공간에서 절대 풀지 못할 질문(또는 알지 못함floyd's turtle and hare )

의문:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

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

질문 설명

이 질문의 등급은 보통입니다. 특히 141. Linked List Cycle 또는 142. Linked List Cycle 을 해결한 적이 없는 경우 정확하지 않습니다. Robert W. Floyd 자신이 아니라면 이 두 가지 문제를 모두 해결하는 방법을 모르면 해결이 불가능하다고 말할 수 있습니다.

그렇다면 이 질문을 실제로 어떻게 해결할 수 있을까요? floyd's turtle and hare은 이 질문을 제가 이해하는 유일한 방법입니다.
알겠습니다. Turtle & Hare 접근 방식으로 해결할 수 있습니다. 하지만 당신이 묻는 게 도대체 뭐죠?

Floyds Turtle & Hare는 루프백하는 노드를 찾기 위해 설계된 알고리즘입니다. 즉, 목록에서 주기를 감지합니다. 일반적으로 Linked List에서 이 작업을 수행하지만 이번에는 배열로 위장한 Linked List가 있습니다. 여기서 nums[i]는 다음 노드를 나타냅니다.

어떻게 작동합니까?
그 배후의 수학은 복잡합니다. 직접 확인하십시오: Proof ;
;

기본적으로 한 번에 하나의 포인터를 1노드씩 이동하고(느리게) 또 다른 포인터를 두 배의 속도로 이동하는 경우(빠름), 우리의 빠른 속도는 결국 주위를 맴돌다가 느리게 착륙할 것입니다. 즉, 속도 차이로 인해 만날 수 없어 루프가 발생했습니다. 따라서 우리는 빠른 포인터를 다시 시작점으로 이동하고 포인터가 다시 만날 때까지 한 번에 1노드씩 이동합니다. 그들이 다시 만날 때도 마찬가지입니다. 그들은 항상 루핑 노드에서 만날 것입니다.

이를 달성하기 위한 코드는 매우 간단합니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 순회하는 목록의 길이입니다.

공간 복잡도: O(1) | 우리는 여분의 공간을 사용하지 않습니다.

리트코드 결과:

제출 링크 참조:

해결책

var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    fast = 0;

    do {
        slow = nums[slow];
        fast = nums[fast];
    } while (slow != fast);

    return slow
};