(LeetCode) Single Number

Single Number

  • 분류 : Array
  • 난이도 : Easy

Problem

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

Example 1

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

Example 2

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

Example 3

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

Constraints

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

Solution 1

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
fun singleNumber(nums: IntArray): Int {
var set = mutableSetOf<Int>()
nums.forEach {
if (set.contains(it)) {
set.remove(it)
} else {
set.add(it)
}
}
return set.toIntArray()[0]
}
}

Solution 2

Exapnder
1
2
3
4
5
6
7
8
9
class Solution {
fun singleNumber(nums: IntArray): Int {
var number = 0
nums.forEach {
number = number xor it
}
return number
}
}

Point of Thinking

  • 단, 하나의 숫자를 제외하고 모든 숫자는 짝이 존재한다.
    • 단순하게 생각한다면, 중복 제거는 역시 집합으로 처리하는 것이 편할 수 있다.
    • 단, 집합은 인덱스가 없으므로 문제의 특성상 하나의 숫자만 남았다고 가정하고, [0] 번째 인덱스를 반환시켜서 Accepted할 수는 있다.
  • 좀 더 본질로 돌아가서, 결국 문제가 원하는 것은 중복되는 숫자의 소멸이다.
    • 중복되는 숫자를 제거하는 방법은 뭐가 있을까?
      • 모든 값을 순회하며 중복되는 숫자를 지우는 것, 딱 봐도 worst case.
      • 중복되는 값은 비트 연산을 통해 전부 제거할 수 있다. -> 모든 원소들에 대해서 0으로 XOR 처리