LeetCode 136번 Single Number
LeetCode 136번 Single Number

 

목차

문제 문제 링크

비어있지 않은 정수 배열 `nums`가 주어집니다. 이 배열에서 하나의 원소를 제외한 모든 원소는 두 번씩 나타납니다. 한 번만 나타나는 원소를 찾아 반환하세요.

입력

정수 배열 `nums`가 주어집니다.

예제 입력 1

nums = [2,2,1]

예제 입력 2

nums = [4,1,2,1,2]

출력

한 번만 나타나는 원소를 반환합니다.

예제 출력 1

1

예제 출력 2

4

풀이

문제 해결 방법

이 문제는 XOR 비트 연산을 사용하여 효율적으로 해결할 수 있습니다. 주요 해결 방법은 다음과 같습니다:

  1. XOR 비트 연산을 이용한 해결 방법:
    • XOR 연산의 특성을 이용 (a ^ a = 0, a ^ 0 = a)
    • 모든 원소를 XOR 연산하면 한 번만 나타나는 원소만 남음
  2. 해시 테이블을 이용한 해결 방법:
    • 각 원소의 등장 횟수를 해시 테이블에 저장
    • 한 번만 나타나는 원소를 찾아 반환

XOR 방법의 시간 복잡도는 O(N)이고, 공간 복잡도는 O(1)입니다.

코드

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