136. Single Number

https://leetcode.com/problems/single-number/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

최초 풀이는 HashMap을 이용해서 배열의 요소의 개수를 체크한 후 개수가 1인 요소를 반환했다.

하지만 이렇게 풀이할 경우 공간 복잡도가 O(n)이었다.

 

문제에서는 공간복잡도 O(1)로 풀길 권장하고 있었기 때문에 풀이를 좀 찾아보았다.

 

그 결과 아래와 같이 xor 연산을 이용해보았다. 

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int num: nums) {
            result ^= num;
        }
        return result;
    }
}

 

xor 연산은 베타적 논리합이라고 하며 아래와 같은 규칙을 가진다.

그림 (https://sabarada.tistory.com/160) 

[LeetCode] Single Number 개인풀이

 

따라서 요소가 두 개인 경우에는 0이 되고

요소가 한 개인 경우에는 0과의 베타적 논리합이 요소 그 자체가 되므로 풀이에 사용하면 된다.