[알고리즘] 287. Find the Duplicate Number

프최's log·2020년 12월 13일
0

study

목록 보기
53/59

문제 설명

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

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

제한사항

  • 2 <= n <= 3 * 104
  • 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.

알고리즘

알고리즘을 2개 활용했다.

Method1

1.중복 검사할 객체를 만든다.
2.객체의 값이 2 이상 되는 key를 반환한다.

Method2

1.중복을 제거한 배열을 만든다.
2.해당 배열과 기존 nums 배열을 비교해서 nums 배열에 없는 원소를 반환한다.

구현

Method1

var findDuplicate = function(nums) {

  let findDupObj = {};
  
  for (let i=0; i < nums.length; i++){
    if(nums[i] in findDupObj){
      findDupObj[nums[i]]++;
    }
    else {
      findDupObj[nums[i]]=1;
    }
  }

  for(let key in findDupObj){
    if(findDupObj[key] >= 2){
      return key;
    }
  }
  
};

Method2

var findDuplicate = function(nums) {

  let compareArr = [...new Set(nums)];
  for(let i=0; i < nums.length;i++){
  if(nums[i] !== compareArr[i]){
     return nums[i];
  }
}
};

다른 사람 풀이

profile
차곡차곡 쌓아가는 나의 개발 기록

0개의 댓글