[JS] 136. Single Number

문제 링크: https://leetcode.com/problems/single-number/
난이도: Easy

 

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.

 

비어 있지 않은 정수 배열이 주어지면 모든 요소는 하나를 제외하고 두 번 나타납니다. 그 하나를 찾으십시오.
선형 런타임 복잡성이 있는 솔루션을 구현하고 일정한 추가 공간만 사용해야 합니다.

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

---

문제 풀이

연관 주제: Bit Manipulation 비트 조작하기

 

* 비트연산자  XOR 작동 원리

XOR은 입력값이 서로 다르면 True(1), 서로 동일하면 False(0)를 반환한다.

즉, 두 수가 같은 숫자면 0이 되기 때문에 나오는 두 번 나오는 숫자들은 0으로 초기화되고, 결과값은 중복이 없는 Single Number가 나오는 것

//반복되지 않는 숫자 찾기

//filter() > indexOf(),lastIndexOf()
var singleNumber = function(nums) {
    return nums.filter(i=>nums.indexOf(i)===nums.lastIndexOf(i));
};
//계산속도 느려서 좋은 풀이는 아닌 것 같으나 일단 시도해본 풀이라서 써 봄

//reduce() > 비트연산자 XOR(^)
var singleNumber = function(nums) {
    return nums.reduce((a,b)=>a^b);
};

//for문 > 비트연산자 ^=
//좌항과 우항의 논리식이 서로 다르면 왼쪽 피연산자에 true을 대입하고, 그 외에는 false을 대입함.
var singleNumber = function(nums) {
    let result;
    for (let i=0;i<nums.length;i++){
        result^=nums[i];
    }
    return result;
};

---

연관 주제로 bit manipulation 이 있어서 찾아보니 이쪽 자료는 C++ 쪽에 정리가 잘 되어 있어서 mdn보다는 이쪽을 참고해서 공부해두는 게 좋을 듯 하다. 자바스크립트 mdn 문서 설명이 너무 간략해서 바로 원리를 이해하기 쉽지가 않다.. (근본적인 원리는 동일한 모양이니 연산자 작동 방식 이해에 도움이 될 것이락 생각한다)