[LeetCode] 287 Find the Duplicate Number JavaScript

문제 링크

Find the Duplicate Number - LeetCode

 

문제 유형

배열

 

문제 풀이

이 문제는 배열 내 중복되는 숫자를 찾아 리턴하는 문제이다. 이 문제는 배열 내의 요소를 인덱스로 보는 방법을 통해 O(n)의 시간복잡도를 갖지만 공간복잡도가 다른 두 방법으로 접근할 수 있다.

• 새로운 배열에 숫자 존재 여부를 표시하기
  nums 배열의 길이의 배열을 만들고, 배열을 순차적으로 접근한다. 현재 숫자에 해당하는 인덱스에 1을 표시한다. 만약, 현재 숫자에 해당하는 인덱스에 이미 1이 있으면 중복된 것으로 간주하고 해당 요소를 리턴한다.
  이는 새로운 배열을 만들어야 하므로 O(n)의 공간복잡도를 갖는다.
  
  
• 숫자 존재 여부를 음수로 표시하기
  배열을 순차적으로 접근하면서 현재 숫자에 해당하는 인덱스의 요소에 -1을 곱한다. 만약 인덱스의 숫자가 이미 음수이면 중복된 것으로 간주하고 현재 숫자를 리턴한다.

 

다음과 같은 배열이 있다.

1

3

4

2

2

i = 0) 숫자는 1이므로 인덱스 1의 값을 음수로 바꾼다.

1

-3

4

2

2

i = 1) 숫자는 3이므로 인덱스 3의 값을 음수로 바꾼다.

1

-3

4

-2

2

i = 2) 숫자는 4이므로 인덱스 4의 값을 음수로 바꾼다.

1

-3

4

-2

-2

i = 3) 숫자는 2이므로 인덱스 2의 값을 음수로 바꾼다.

1

-3

-4

-2

2

i = 4) 인덱스 2의 값은 이미 음수이므로 2가 중복되는 숫자이다.

1

-3

-4

-2

-2

 

코드

// 1
var findDuplicate = function(nums) {
    const array = new Array(nums.length);
    
    for (let i = 0; i < nums.length; i++) {
        if (array[nums[i]] === 1) {
            return nums[i];
        }
        array[nums[i]] = 1;    
    }
    return 0;
};

// 2
var findDuplicate = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        const num = Math.abs(nums[i]);
        if (nums[num] < 0) return num;
        nums[num] *= -1; 
    }
    return 0;
};

 

참고

https://www.youtube.com/watch?v=k6rsok-7zNA