LeetCode 442

Find All Duplicates in an Array

문제 출처

문제

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

나의 코드 1

Extra space (hashTable) 를 사용한 O(N) 시간의 코드

추가 공간을 사용했지만 코드 가독성 면에서는 뛰어나다.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
  const hashTable = {};

  return nums.filter((cur) => {
    if (hashTable[cur]) {
      return true;
    } else if (!hashTable[cur]) {
      hashTable[cur] = true;
    }
  });
};

나의 코드 2

문제의 추가 요구사항대로 O(N) 시간 복잡도와 Extra place 을 사용하지 않은 코드
1 ≤ a[i] ≤ n (n = size of array) 조건이 있기 때문에 사용할 수 있었던 방법이다.
(각 배열 요소들은 배열의 길이를 넘지 않는 값을 가진다.)

문제 요구사항을 모두 충족하긴 하지만 코드 가독성은 그리 높지 않다.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
  // 두 번 존재하는 요소를 찾아내기 위해 배열 요소를 변형하는 부분
  // 1. loop 마다 현재 요소의 값을 index 로 사용한다.
  // 2. 한번도 방문하지 않은 요소와 구별하기 위해 현재 index 요소에 + length 해준다.
  //    (방문하지 않은 요소만 <= length 가 된다.)
  // 3. 두번 방문인지 구분하기 위해 현재 index 요소에 * -1 해준다.
  nums.forEach((cur) => {
    let index = Math.abs(cur) - 1;
    if (index >= nums.length) index -= nums.length; // 이미 + length 해준 요소는 - length 를 해서 index 로 사용한다.

    // 2. 방문하지 않은 요소일 경우 + length 해준다.
    if (Math.abs(nums[index]) <= nums.length) nums[index] += nums.length;
    // 3. * -1 해준다.
    nums[index] *= -1;
  });

  return nums
    .map((cur, idx) => {
      // 한번이라도 방문한 (cur > length) 요소이면서 양수 (* -1 이 두번 됨) 일 경우만
      // 해당 요소의 index 에 + 1 한 값을 배열에 남긴다.
      if (cur > nums.length) return idx + 1;
    })
    .filter((cur) => cur !== undefined); // .map() 에서 return 되지 않은 요소드을 걸러낸다.
};

참고 코드

추가 공간을 사용했지만 O(1) 공간을 가지는 코드이다.
시간은 O(N) 이다.

추가 공간 사용 외에 * -1 을 사용한 구분은 나의 코드와 동일하다.

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

배운점