287. Find the Duplicate Number

287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2
Example 2:

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

Constraints:

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

1. Time Limit Exceeded 발생

function findDuplicate(nums: number[]): number {

  let target = 0
  let count = 0

  while (nums.length !== 0) {
    var primary = nums.shift()
    var cnt = 0
    for (let i=0; i<nums.length; i++) {
      if (primary === nums[i]) {
        target = primary
        cnt++
      }
    }

    if (cnt > count) {
      primary = target
      count =cnt
    }
  }

  return target
};

2. Set 사용

function findDuplicate(nums: number[]): number {
  let len = nums.length
  let set = new Set()

  for(let i=0; i<len; i++) {
    if (set.has(nums[i])) { 
      return nums[i]
    }
    set.add(nums[i])
  } 
  return -1
};