LeetCode 442 - Find All Duplicates in an Array ( JavaScript )

 

안녕하세요 besforyou입니다

 

이번 글은 LeeCode 442 - Find All Duplicates in an Array ( JavaScript ) 풀이입니다

---

문제 한글 해설

 

길이가 n인 정수 배열 nums 이 있는데 배열의 모든 원소 범위는 [ 1 , n ]이고 각 원소는 한 번 또는 두 번 나타난다.

 

두 번 나타나는 원소로 이루어진 배열을 반환하라.

 

단, 시간 복잡도가 O(n)이고 constant extra space를 이용해야 한다.

 

여기서 constant extra space는 공간 복잡도가 O(n)가 아닌 O(1)을 말합니다.

 

---

문제 풀이

 

간단하게 정렬 알고리즘, Brute-Force(단순 무식 법) , Map을 사용하는 알고리즘을 떠올릴 수 있지만 요구조건을 충족하지는 못합니다.

 

 

1. 배열을 정렬하는 풀이

 

배열을 정렬한 뒤, 순차적으로 탐색하며 중복된 원소를 배열에 넣어서 반환하는 풀이입니다.

 

시간 복잡도 - O(N * logN)

공간 복잡도 - O(1)

 

var findDuplicates = function(nums) {
    
    let ans = [];
    
    nums.sort(function(a, b) {
        return a - b;
    })
 
    for (let i = 1; i < nums.length ; i++) {
        if (nums[i] == nums[i-1]) ans.push(nums[i]);
    }
    return ans;
}

 

 

 

2. Brute-Force ( 단순 무식 법 )

 

배열의 원소를 순차적으로 참조하면서 배열의 원소가 배열에 중복이 되는지 하나하나 모두 탐색하는 방법입니다.

 

구현은 쉬우나 시간 복잡도는 좋지 않은 편입니다.

 

시간복잡도 - O(N * N)

공간 복잡도 - O(1)

 

var findDuplicates = function(nums) {
    
    let ans = [];
    
    for (let i = 0 ; i < nums.length ; i++) {
        let num = nums[i];
        for (let j = 0 ; j < nums.length ; j++ ) {
            if (i == j) continue;
            let num2 = nums[j];
            if (num == num2) ans.push(num);
        }
    }
    
    return ans;
}

 

 

 

 

3. Map을 사용

 

Map을 이용하여 key - value pair를 저장하는 풀이입니다.

 

배열을 순차적으로 탐색하고 배열의 원소를 key, 해당 원소의 개수를 value로 사용하는데, Map에 현재 참조하는 원소를 key로 하는 key -

 

value 가 없다면 추가하고, 있다면 정답 배열에 추가합니다. 저는 메모리 사용량을 줄이기 위해 Map 대신 배열을 사용했습니다. 알고리즘

 

은 똑같습니다.

 

시간 복잡도 - O(N)

공간 복잡도 - O(N)

 

var findDuplicates = function(nums) {
    
    let len = nums.length
    let arr = new Array(len+1).fill(0)
    let ans = [];
    
    for (let i = 0 ; i < len ; i++) {
        let num = nums[i];
        if (arr[num] == 0) arr[num] = 1;
        else if (arr[num] == 1) ans.push(num);
    }
    
    return ans;
}

 

 

 

그렇다면 시간 복잡도가 O(N)이고 추가적인 O(N) 메모리 공간이 필요 없는 알고리즘은 무엇일까요?

 

 

 

4. 가장 좋은 알고리즘

 

주어진 nums 배열의 특징을 이용하고, nums 배열을 순차적으로 탐색하며 정답 배열을 생성하는 알고리즘이 있습니다.

 

nums 배열의 원소들은 1 이상 n 이하인 점을 이용하여 배열의 (원소값 - 1 )을 배열의 인덱스로 사용하고 해당 인덱스의 원소 값이 양수면 

 

중복되지 않은 값으로 보고 해당 원소 값에 -1을 곱해서 음수로 만듭니다. 해당 인덱스의 원소 값이 음수라면 이미 한번 본 적이 있는 값인 것

 

을 의미하므로 정답 배열에 원소 값을 추가합니다.

 

시간 복잡도 - O(N)

공간 복잡도 - O(1)

 

var findDuplicates = function (nums) {
    if (nums.length == 0) return [];
    
    let ans = [];
    
    for (let i = 0 ; i < nums.length ; i++) {
        if(nums[Math.abs(nums[i]) - 1] < 0)
            ans.push(Math.abs(nums[i]));
        nums[Math.abs(nums[i])-1] = nums[Math.abs(nums[i])-1] * -1;
    }
    
    return ans;
}

---

결과