[Easy] 136. Single Number

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

Single Number - LeetCode

문제

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.

 

풀이 과정

loop를 통해 문제를 해결해보았다.

• nums의 유일 값을 구할 arr 배열을 생성한다.
• num를 완전탐색하는 for문을 돈다
  • 만약 arr배열에 nums[i]값이 없다면, arr에 nums[i]을 저장한다.
  • 만약 arr배열에 nums[i]값이 있다면, arr에서 nums[i]를 뺀다.
• 이러한 과정을 거치고 나면 유일 값 하나만 arr에 저장이 되어있을 것이다.
• 유일값 arr[0]을 반환한다.

비트 연산자를 이용한 코드도 가져와보았다.

^ 연산자는 Bitise XOR라고 불린다.

0 ^ 0 = 0;
1 ^ 0 = 1;
0 ^ 1 = 1;
1 ^ 1 = 0;

비트 연산자 활용은 아직 익숙치 않다고 느껴진다. 

비트 연산자는 조금 더 공부한 후 다시 도전해보아야겠다!

 

풀이 코드

나의 코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let arr = [];
    
    for(let i = 0 ; i < nums.length ; i++){
        if(!arr.includes(nums[i])){
            arr.push(nums[i]);
        }else{
            let idx = arr.indexOf(nums[i]);
            arr.splice(idx, 1);
        }
    }
    
    return arr[0];
};

 

비트 연산자를 이용한 코드

// time O(n)
// space O(1)
function singleNumber(nums) {
  let num = 0;
  for (let n of nums) {
    num ^= n;
  }
  return num;
}

 

참고 사이트

https://www.youtube.com/watch?v=XzQSPg6LFyY