LeetCode 136. Single Number

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.

빈 배열이 아니고 정수로 이루어진 배열에서, 한 개만 제외하고 모든 요소가 두 번 나타난다.
유일하게 한 번 나타나는 요소를 찾는 문제.

입출력 예

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

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

Input: nums = [1]
Output: 1

제한 사항

• 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.

풀이

나의 풀이

1. 배열 nums 정렬
2. nums 배열을 돌면서 stack에 해당 요소가 있으면 pop() 메서드로 추출
3. 해당 요소가 없으면 push() 메서드로 stack에 추가
4. 유일 요소이기 때문에 인덱스 0에 위치하는 값 return

// Runtime: 79 ms, faster than 88.65%
// Memory Usage: 44.5 MB, less than 68.10%

var singleNumber = function(nums) {
  nums.sort((a, b) => a - b);

  let stack = [];
  for (let i = 0; i < nums.length; i++) {
    if (stack[0] === nums[i]) stack.pop();
    else stack.push(nums[i]);
  }

  return stack[0];
};

다른 풀이

1. nums 배열을 돌면서 ht에 해당 요소가 존재하지 않으면 생성
2. 해당 요소의 값을 1씩 ++
3. ht에서 값이 1인 key 찾아서 return

// Runtime: 134 ms, faster than 31.84%
// Memory Usage: 47.9 MB, less than 17.92%

var singleNumber = function(nums) {
  let ht = {};
  for (let num of nums) {
    if (!ht[num]) ht[num] = 0;
    ht[num] += 1;
  }

  return Object.keys(ht).find(key => ht[key] === 1);
};

다른 사람들의 풀이

해당 key가 존재할 때 그 key를 바로 삭제해주면 find() 쓸 필요도 없고 훨씬 간단해진다.

var singleNumber = function(nums) {
    let hash = {}
    for(let val of nums){
        hash[val] ? delete hash[val] : hash[val] = 1;
    }
    return Object.keys(hash)[0]
};

Set을 이용한 풀이
next()는 처음 봐서 찾아봤더니 Iterator의 내장 메서드라고 한다. Set.value()를 통해 Iterator로 만들어준 다음, next()를 호출하면 { value: value, done: true/false } 형태로 반환한다.

var singleNumber = function(nums) {
  let hash = new Set();
  nums.forEach(n => {
    if(!hash.has(n)) hash.add(n);
    else hash.delete(n);
  });

  return hash.values().next().value;
};

console.log(hash) // Set(1) { 4 }
console.log(hash.values()) // [Set Iterator] { 4 }
console.log(hash.values().next()) // { value: 4, done: false }
console.log(hash.values().next().value) // 4

XOR 연산자를 이용한 풀이
비트 연산 공부하고 다시 볼 예정

function singleNumber(nums) {
  let num = 0;
  for (let n of nums) {
    num ^= n;
  }
  return num;
}

function singleNumber(nums) {
	return nums.reduce((prev, curr) => prev ^ curr);
}

WIL

1. delete obj[val]

객체 사용보다 배열 사용에 훨씬 익숙해져있다 보니, 객체에서는 delete로 바로 삭제가 가능하다는 것을 자주 잊어버린다.

2. next()

Iterator의 내장 메서드인 next()는 다음 두 속성을 갖는 객체를 반환한다.

• done: 반복이 끝났는지의 여부
• value: - 현재 순서의 값

{ value: value, done: true/false }