[LinkedList][Medium] 287. Find the Duplicate Number

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

 

아래와 같은 정수 배열이 주어질 때 단 하나의 중복 값이 존재한다. 

이 값을 찾아라. 

 

입력 배열을 수정하지 말고, 추가 메모리를 사용하지 말라.

 

이 문제가 linked list category인 이유가 있다. 

따라서 해석이 중요한 문제다. 

 

각 원소가 다음 원소의 index의 위치라고 한다면, 

중복되는 값은 cycle의 시작 지점을 의미한다. 

 

우선, cycle이 존재하는 지 판단하고, 그 지점을 찾는다.

찾고 cycle의 시작점을 찾는다. 

 

그러면 답이 찾아진다.

 

코드

int findDuplicate(vector<int>& nums) 
{
    int idxFast = 0;
    int idxSlow = 0;   
    bool start = false;
    bool hasCycle = false;
    while(idxFast<nums.size() && nums[idxFast]<nums.size())
    {
        if(start && nums[idxSlow]==nums[idxFast])
        {
            hasCycle = true;
            break;
        }
        idxSlow = nums[idxSlow];
        idxFast = nums[ nums[idxFast] ];
        start = true;
    }
    if(!hasCycle)   return -1;

    idxFast = 0;
    while(true)
    {
        if(nums[idxSlow] == nums[idxFast])
            return nums[idxSlow];

        idxSlow = nums[idxSlow];
        idxFast = nums[idxFast];
    }
    return -1;
}

 

 

 

결과