[LeetCode] Find the Duplicate Number

문제

https://leetcode.com/explore/featured/card/june-leetcoding-challenge/542/week-4-june-22nd-june-28th/3371/

중복된 숫자를 return 하면 되는 간단한 문제다.
대신 array를 수정하면 안 되고, O(n2) 보다 작은 시간 복잡도를 써야한다.
그리고 공간복잡도는 O(1)이여야 한다고 한다.
중복된 숫자는 한개가 있다.

풀이

이런 문제는 Object나 Map을 활용하여 각각 개수를 센 다음에 출력하는게 제일 좋은 것 같다. 그래서 그렇게 풀었는데 이거는 공간복잡도가 O(1)이 아니라고하는 거 같다... 하지만 코드 자체는 마음에 든다...

코드

const findDuplicate = function (nums) {
  const numsMap = new Map();

  nums.forEach((num) => {
    numsMap.set(num, 1 + (numsMap.get(num) || 0));
  });

  return [...numsMap.entries()].filter((entry) => entry[1] > 1)[0][0];
};

다른 사람의 코드

e의 index와 nums에서 indexOf를 하면 제일 처음 index가 나오기 때문에 다른 것은 중복 됐을 때의 값이다.라는 것을 의미하는 것 같다. 그런데 find도 반복문이고 indexOf도 반복문이라 O(n2)이지 않을까 하지만... 일단 이 코드도 한줄이라 굉장히 깔끔하고 좋은 것 같다.

var findDuplicate = function(nums) {
    return nums.find((e,i)=> nums.indexOf(e)!=i)
};