(LeetCode) 136. Single Number
Single Number
- Explore : Interview > Top Interveiw Questions > Easy Collection
- 분류 : 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 처리
