136. Single Number

Hyunmin·2024년 4월 11일

leetcode

LeetCode

목록 보기

4/5

문제 설명

비어있지 않은 숫자배열이 주어졌을때, 해당 배열안에는 특정 원소 하나를 제외하고 2번 나타난다. 한번만 나타나는 원소를 찾아야한다!

조건

선형적인 시간복잡도 O(N)의 알고리즘이어야 함
정해진 공간복잡도만을 활용해야함

나의 풀이

계수정렬(counting sort)와 비슷한 원리로 접근함

해당 문제의 숫자 범위는 음의 값도 포함하기에, 해당 음의값을 양의 값으로 바꿔주는 과정이 필요함

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> list(60001, -1);
        int len = nums.size();
        for(int i = 0; i< len; i++){
            if(nums[i] < 0){
                list[nums[i] + 60001]++;
            }
            else{
                list[nums[i]]++;
            }
        }
        for(int i = 0; i< 60001; i++){
            if(list[i] == 0){
                if(i >= 30001){
                    return i - 60001;
                }
                return i;
            }
        }
        return 1;
    }
};

한계점

속도 적인 측면에서 시간복잡도가 O(N)으로 빠른 알고리즘이지만, 공간복잡도 측면에서 불필요한 공간이 많이 사용됨

Solution

XOR 연산 이용!

XOR(^) 연산이란?

두개의 비트가 같으면 0, 다르면 1을 출력하는 비트연산자!

성질

교환법칙
결합법칙
항등원 [ X ^ 0 = X ]
X ^ X = 0

Example

input: 3 5 2 4 4 5 3

3 ^ 5 ^ 2 ^ 4 ^ 4 ^ 5 ^ 3
= (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5) ^ 2 (by 교환 및 결합법칙)
= 0 ^ 0 ^ 0 ^ 2
= 2 (by 항등원)

코드 구현

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for(int i = 1; i < nums.size() ; i++){
            nums[0] ^= nums[i];
        }
        return nums[0];
    }
};