[LeetCode][JS] 136번 Single Number

문제 유형

배열, 비트 연산

 

문제

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

비어있지 않은 숫자를 담은 배열이 주어진다. 배열에서 2번 나타나지않은 요소를 찾아라. 

반드시 선형 시간 복잡도로 풀어야 하며 O(N)가 아닌 O(1) 시간으로 풀어라 

 

constant extra space
- 사용하는 메모리 영역의 constant 제약이 있음
  - 즉, 입력값에 따라 변하는 variable 이 아님
  - 주의: 입력 데이터 외에 사용하는 메모리 영역에 관한 것으로 추정됨
         왜냐하면 그렇지 않은 경우, 입력이 array 인 경우 바로 O(N) 이 됨

예시

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

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

Input: nums = [1]
Output: 1

 

풀이

XOR(^) 비트 연산자를 사용하면 된다.

 

XOR 연산자는??

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

위와 같이 XOR연산자는 a와 b가 다르면 1을 리턴, 같으면 0을 리턴한다.

 

문제는 배열안에 같은 숫자가 2회 반복되므로 순서에 상관없이 2회 같은 숫자가 오면 a ^ a = 0이 나오게 되고 마지막으로 1번만 나온 숫자가 연산자의 값으로 나오게 된다!

이를 이용해서 문제를 풀면된다

 

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
 
var singleNumber = function (nums) {
  return nums.reduce((a, b) => a ^ b);
};