LeetCode(Single Number)

url : https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/549/

 

위 문제는 배열에서 한 숫자를 제외한 나머지 숫자는 2개가 있으며, 한 숫자는 1개만 존재하며, 이숫자가 어떤 숫자인지 찾는 문제

 

처음 문제를 풀었을때는 짝수니 배열을 생성해서 넣고, 빼버리면 남은건 하나만 있지 않을까?

위와 같은 생각을 가지고 풀었다. 하지만 조건이 시간복잡도는 O(n), 공간복잡도 O(1)을 요구해서 위 경우 처럼 풀었을 경우 시간 복잡도는 만족하지만 공간복잡도를 만족하지 못한다. 공간 복잡도를 O(1)로 만들기 위해서 다른 방법을 찾았고 다음과 같은 힌트를 보고 문제를 새로 풀었다.

문제 풀이 방법

1. 비트연산중 XOR방식으로 중복된 값을 제거

2. 마지막 남은 값이 결국 중복되지 않은 한 값임

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;

        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
}

 

 

 

비트연산인란 

컴퓨터에서 이진수(bit) 단위로 수행하는 연산

 

비트연산 종류

연산자	연산기능
&	비트단위 AND 연산을 함
|	비트단위 OR 연산을 함
^	비트단위 XOR 연산을 함
~	단항 연산자로서 피연산자의 모든 비트를 반전시킨다
<<	피연사자의 비트열을 왼쪽으로 이동시킨다
>>	피연사자의 비트열을 오른쪽으로 이동시킨다