2020.08.25 Single number 풀이 (feat. 비트 연산자)

어제 풀었던 싱글 넘버 추출하는 문제. 어제 도저히 운동갔다와서 블로깅까지 할 체력이.. 아니었다^^ (핑계룰루!)

 

문제) 숫자가 담긴 배열이 주어진다. 이때 배열의 숫자는 2번 중복된다. 이때, 중복되지 않은 배열의 값은 무엇인가?

제약) O(n)과 별도의 공간을 쓰지 말것. (별도의 공간을 쓰지 말라는게 자바스크립트에서 의미 있는 말일까?) 

풀이) 처음으로 정해진 시간 안에 문제를 풀었다! ^^ 배열을 우선 크기 순으로 정렬하고 -> 옆의 원소와 동일하면, 그 같은 원소 모두 삭제 -> 옆 원소와 다를 경우 return 한다.

 

배열인 array 도 결국 object의 일환이기 때문에 delete 키워드를 쓸 수 있다. splice가 아닌 delete를 쓴 이유는 배열의 원소가 삭제되면서 순서가 교란될까봐였다. delete를 쓰면 해당 공간은 undefined 된 채로 순서는 그대로 남아있게 된다. 

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    nums = nums.sort((a,b) => a - b);
    for(let i = 0; i < nums.length; i++){
      if(nums[i] !== undefined ){
        if(nums[i] === nums[i+1]) {
          delete nums[i]
          delete nums[i+1]
        } else {
          return nums[i]
        }
      }
    }
};

 

그리고 난 뒤, 다른 풀이도 살펴 보았다.

 

1) Math

 a+ b+ a+ c+ b+ d + c = 2(a+b+c +d) - d

var singleNumber = function(nums) {
  let arr = [], sum = 0; mid = 0;
  for(let i = 0; i < nums.length; i++) {
     sum += nums[i]
     if(!arr.includes(nums[i])){arr.push(nums[i])}
     else {mid += nums[i]}
  }
  return sum - 2* mid
};

 

2) bit manipulation (2진수를 이용한 계산)

1 ^ 0 = 1

0 ^ 1 = 1

1 ^ 1 = 0

 

var singleNumber = function(nums) {
  let sum;
  for(let i = 0; i < nums.length; i++) {
    sum ^= nums[i]
  }
  return sum;
}

 

a ^ b ^ c = c^ b ^a 순서 상관 없이 답은 같다

(a^b)^c = a^(b^c) 도 관계 없다. 

 

공감한다...후^^

 

https://leetcode.com/problems/single-number/

Single Number - LeetCode