[Leetcode] 287. Find the Duplicate Number

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

Leetcode - Find the Duplicate Number

문제 유형 : 배열, 연결리스트, 투 포인터

문제 난이도 : Medium

 

문제

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.

 

nums 배열에 n+1개의 정수를 1 ~ n의 범위에서 담았다.

배열을 수정할 수 없고, 상수 공간만을 사용하여 반복된 수를 반환하라.

 

풀이

비둘기집의 원리에 의해, 적어도 하나 이상의 중복수들이 존재한다.

사실 이 문제는 배열로 주어지는 것 같아 보여도, 연결리스트이다.

값이 다음을 가리키는 인덱스라고 생각하자.

그리고, 두 칸씩 이동하는 fast노드, 한 칸씩 이동하는 slow노드를 만든다.

둘이 같은 값을 가질 때 까지 계속 이동시킨다. 중복되는 수가 반드시 존재하므로, 둘은 반드시 만난다.

사이클이 반드시 생긴다는 뜻이다.

 

둘이 만나면, slow를 처음으로 돌리고, slow와 fast를 같이 한 칸씩 이동시켜서 둘이 만날때까지 기다린다.

둘이 만나는 그 지점이 사이클의 시작점으로, 중복되는 수라는 뜻이다.

 

코드

C++

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

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

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

        return slow;
    }
};