Algorithm/문제풀이
[Leetcode] 136. Single Number 문제 풀이
bluespacedev
2021. 9. 12. 21:30
https://leetcode.com/problems/single-number/
Single Number - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 내용
배열에 2개씩 숫자쌍이 있는데 혼자만 있는 숫자 찾기
Example 1:
Input: nums = [2,2,1]
Output: 1
문제 풀이
hash로 count 하는 단순한 방법은 공간 복잡도가 O(n) 만큼 든다.
공간 복잡도가 O(1) 만큼 하는 방법이 있다.
xor 연산자를 활용하는 방법이다.
xor 은 같으면 0이 되는 연산이다.
x ^ y ^ x 를 연산했을 때
(x ^ x) ^ y 와 같은 결과를 얻을 수 있다.
그래서 순차적으로 xor 연산만 해주면 된다.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto num : nums)
ans = ans ^ num;
return ans;
}
};