[Leetcode][Java] 287 Find the Duplicate Number

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.

 

Example 1:

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

n+1개 integer를 가지고 있는 nums 배열이 주어진다.

각각의 원소의 범위는 [1, n]이다.

오직 하나의 숫자만 반복이 되는데, 그 숫자를 반환하라.

주어진 배열을 수정하지 말고, 추가적인 공간도 상수 개만 사용해서 문제를 풀어라.

---

해당 문제를 풀기 위해서는 Set, Map과 같은 추가적인 공간을 사용할 수도 있고,

Sorting을 통해서 인접한 원소들을 비교할 수도 있다. 

다만, 문제의 조건이 추가적인 공간이 상수 개이고, 정렬도 없다는 조건이므로 이러한 방식 이외의 것이 필요하다.

이 문제에서 중요하게 볼 부분은 배열에 주어진 값이 배열 인덱스 내의 값이라는 것이다.

즉, 배열의 값을 통해서 다른 배열로 포인팅이 가능해지고 해당 과정을 반복하며 2번 방문한 곳을 찾을 수 있다.

두 번 반복했는지 확인하기 위해서는 추가적인 공간을 사용하지 않고 주어진 배열을 활용할 수 있다.

방문한 배열의 값에 마이너스 표시 , 방문했을 때 배열의 값이 음수이면 중복 방문

 

    public int findDuplicate(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            int tmp = Math.abs(nums[i]);

            if (nums[tmp] < 0) {
                return tmp;
            } else {
                nums[tmp] = -nums[tmp];
            }
        }

        return -1;
    }