[LeetCode] Array101 - Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2:

Example 2:

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

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

* Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

 

---

 

드디어 Array101 시리즈의 마지막 문제다! 🎉

 

문제는 다음과 같다.

 

- 예를 들어 5개의 숫자가 들어있는 배열이 주어진다고 가정해보자. => [5, 2, 3, 3, 5]

- 이 배열에는 1부터 5까지의 숫자만 들어있는데, 1부터 5 중에서 배열에 들어있지 않은 숫자들만 모아서 리턴하는 문제이다. => [1, 4]

 

---

 

물론 가장 쉽게 푸는 방법은 새로운 배열을 만든 다음 비교하는 것이다.

 

- 1부터 5까지 들어있는 배열을 만들고 => [1, 2, 3, 4, 5]

- 주어진 배열을 순회하면서 나온 아이템들을 삭제하는 것이다 => [1, , , 4, ]

- 그리고 숫자가 들어있는 칸만 남겨둔다 => [1, 4]

 

이렇게 풀면 총 3번 순회해야하고, 새로운 배열도 2번 만들어야 한다.

 

처음에 1부터 5까지 든 배열을 만들기 위해 한 번 순회하고,

아이템 삭제하기 위해 한 번 순회하고,

숫자가 들어있는 칸만 남기기 위해 한 번 순회해야한다.

 

문제에서 Follow up을 보면 여분의 메모리 공간 없이 in-place로

O(n) 시간 복잡도를 가지면서 해결하는 방법을 생각해보라고 적혀 있다.

 

그래서 어떻게 하면 그렇게 해결할 수 있을까 고민만 30분 넘게 하다가 다음과 같은 방법을 생각해냈다..!

 

---

 

 

[5, 2, 3, 3, 5]

배열의 각 인덱스에 1을 더하면 바로 배열에 들어갈 숫자의 범위가 된다는 것을 이용할 것이다.

 

[5, 2, 3, 3, 5]

첫 시작 인덱스는 0이다.

 

0번 아이템은 5이다. 그렇다는 뜻은 (5 - 1)번째 숫자는 배열에 들어있으므로 후보에서 탈락한다는 뜻이다.

 

[5, 2, 3, 3, 5]

👇

[5, 2, 3, 3, undefined]

그렇기 때문에 4번째에 든 숫자를 0번째로 옮기고 4번째 칸은 undefined를 할당해서 비워둔다.

 

[5, 2, 3, 3, undefined]

아직 0번째 아이템에 숫자가 있으므로 다시 0번째 아이템을 검사한다.

이번에도 0번째 아이템은 5다. 그러나 (5 - 1)번째 칸은 이미 undefined이다.

 

[5, 2, 3, 3, undefined]

👇

[1, 2, 3, 3, undefined]

그렇기 때문에 0번째 칸에는 (0 + 1)을 한 값을 넣고 시작 인덱스를 1 증가시킨다.

 

 

[1, 2, 3, 3, undefined]

👇

[1, undefined, 3, 3, undefined]

1번째 아이템은 2이다. 그렇다는 것은 (2 - 1)번째 숫자가 후보에서 탈락한다는 뜻이다.

1번째 숫자를 1번으로 옮기고(자기 자신을 덮어 쓰므로 아무 변화도 없다.) 1번째 칸에 undefined를 할당한다.

이제 1번째 칸에 숫자가 없으므로 시작 인덱스를 1 증가시킨다.

 

[1, undefined, 3, 3, undefined]

👇

[1, undefined, undefined, 3, undefined]

2번째 아이템은 3이다. 그러므로 (3 - 1)번째 숫자가 후보에서 탈락한다.

2번째 숫자를 2번으로 옮기고 (역시 자기 자신을 덮어 쓴다.) 2번째 칸에 undefined를 할당한다.

이제 2번째 칸에 숫자가 없으므로 시작 인덱스를 1 증가시킨다.

 

3번째 아이템은 3이다. 그러나 (3 - 1) 번째 숫자는 이미 undefined이다.

 

[1, undefined, undefined, 3, undefined]

👇

[1, undefined, undefined, 4, undefined]

따라서 3번째 칸에는 3 + 1을 한 값을 넣고 시작 인덱스를 1 증가 시킨다.

 

4번째 칸에는 undefined이므로 시작 인덱스를 1 증가시킨다.

그러나 증가된 인덱스가 배열의 마지막 인덱스보다 크기 때문에 종료한다.

 

[1, undefined, undefined, 4, undefined]

최종적으로 위와 같은 배열만 남게 된다. 이제 최종적으로 1번 더 순회하면서 undefined를 제거해주면 끝난다!

 

 

위 방법대로 풀면 in-place이면서 단 한 번의 순회로 결과값이 든 배열을 얻을 수 있으며,

최종적으로 undefined인 값을 필터링만 하면 된다!

 

이 방법을 코드로 풀면 다음과 같다.

 

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
  let index = 0;

  while (index <= nums.length - 1) {
    if (nums[index] === undefined) {
      index++;
      continue;
    }

    const targetIndex = nums[index] - 1;
    
    if (nums[targetIndex] === undefined) {
      nums[index] = index + 1;
      index++;
    } else {
      nums[index] = nums[targetIndex];
      nums[targetIndex] = undefined;
    }
  }

  return nums.filter(num => num !== undefined);
};