Question
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.
My Answer
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
count = nums.count(num)
if count != 2:
result = num
return result
Python
복사
Optimized Version
class Solution:
def singleNumber(self, nums: List[int]) -> int:
unique = 0
for i in nums:
unique ^= i
return unique
Python
복사
XOR 연산의 특성
XOR (^) 연산의 중요한 성질은 다음과 같다:
•
자기 자신과 XOR하면 0이 된다 → a ^ a = 0
•
0과 어떤 값 a를 XOR하면 a가 유지된다 → a ^ 0 = a
•
순서와 상관없이 연산 결과가 동일하다 (결합법칙) → a ^ b ^ c = c ^ a ^ b
주어진 nums 리스트에서 모든 요소를 XOR 하면, 짝수 번 등장한 숫자는 서로 XOR 연산으로 0이 되고,
한 번만 등장한 숫자만 남게 된다.
예제: nums = [4, 1, 2, 1, 2]
연산 과정 | unique 값 |
초기값 0 | 0 |
0 ^ 4 | 4 |
4 ^ 1 | 5 |
5 ^ 2 | 7 |
7 ^ 1 | 6 |
6 ^ 2 | 4 (최종 결과) |
