728x90
1. 문제
https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=leetcode-75
2. 문제 요구사항
1) 정수 배열 nums가 주어진다.
2) 모든 숫자는 두 번식 등장하며, 단 하나만 예외이다.
3) 이 유일한 숫자를 찾는다.
3. 핵심 아이디어
1) XOR 연산
XOR 연산은 같으면 0, 다르면 1을 반환하는 이진 연산이다.
| A | B | A ^ B |
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
여기서 중요한 특징은 다음과 같다.
- 자기 자신과 XOR 하면 0이다.
A ^ A = 0
4 ^ 4 = 0100 ^ 0100 = 0000 = 0
- 0과 XOR 하면 자기 자신이다.
A ^ 0 = A
4 ^ 0 = 0100 ^ 0000 = 0100 = 4
- 자기 자신과 자기 자신을 XOR 하면 0이 된다.
A ^ A = 0
4 ^ 4 = 0100 ^ 0100 = 0000
2) 코드
class Solution {
int singleNumber(List<int> nums) {
int result = 0;
for(int num in nums) {
result ^= num;
}
return result;
}
}
시간 복잡도 : O(n)
공간 복잡도 : O(1)
728x90
'Programming > LeetCode' 카테고리의 다른 글
| [Dart] 202. Happy Number (0) | 2025.03.28 |
|---|---|
| [Dart] 169. Majority Element (Boyer-Moore VoitingAlgorithm) (0) | 2025.03.27 |
| [Dart] 125. Valid Palindrome (0) | 2025.03.25 |
| [Dart] 121. Best Time to Buy and Sell Stock (0) | 2025.03.24 |
| [Dart] 104. Maximum Depth of Binary Tree (0) | 2025.03.21 |