LeetCode 287 - Find the Duplicate Number (Medium)

문제

LeetCode - 287번

풀이 과정

주어진 배열에서 중복된 원소를 찾는 문제입니다.
다만 시간 복잡도가 O(N^2) 보다 낮아야 하며 O(1) 의 추가적인 메모리를 사용해야한다는 제약 조건이 있습니다.

처음에는 비트 마스킹 을 이용해서 문제를 풀려고 했지만 Javascript 에서 비트 연산자를 사용할 경우
피연산자를 32비트로 취급하기 때문에 이를 넘어설 경우 overflow 가 발생했습니다.

이 문제를 해결하는 다른 방법으로는 이분 탐색 이 있습니다.
배열에서 중복된 원소는 오직 하나이며 나머지 원소들은 1 ~ n 의 숫자들 중 하나의 숫자와 매칭되기 때문에
이분 탐색 을 활용해서 중복된 원소를 찾아주기로 했습니다.

특정 기준 값 pivot 보다 같거나 작은 원소의 개수가 pivot 보다 클 경우
pivot 이하의 숫자 중에서 중복된 원소가 존재함을 의미합니다.

따라서 lo & hi 값을 설정해주고 이분 탐색 을 통해 값의 범위를 좁혀나가면서
각각의 pivot 보다 작은 숫자의 개수를 찾는다면 O(NlogN) 에 문제를 해결할 수 있습니다.

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  let lo = 1;
  let hi = nums.length - 1;

  let ans = 0;
  while (lo <= hi) {
    let mid = Math.floor((lo + hi) / 2);

    if (count(nums, mid) > mid) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  return ans;
};

function count(nums, pivot) {
  return nums.filter((e) => e <= pivot).length;
}