[LeetCode] Find the Duplicate Number (C++)

문제 링크: https://leetcode.com/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked 

Find the Duplicate Number - LeetCode

주의할 점

- 이 문제는 Set 또는 정렬을 사용해서 풀지 않도록 한다

- 연결 리스트에서 주기가 시작하는 노드 찾는 방법으로 해결한다

 

구현

- 1칸씩 이동하는 Turtle과 2칸씩 이동하는 Hare(산토끼) 포인터를 통해 순환하는 링크드 리스트에서 만나는 지점을 찾는다

- 배열 처음을 가리키는 포인터 Root를 새로 생성한다

- Root와 Turtle을 1칸씩 이동해서 만나는 지점이 주기의 시작점이다

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

        while (true) {
            turtle = nums[turtle];
            hare = nums[nums[hare]];
            if (turtle == hare) break;
        }
        
        int root = nums[0];
        while(root != turtle){
            root = nums[root];
            turtle = nums[turtle];
        }
        return root;
    }
};