[리트코드] 137. Single Number II .java

[zzu-yaaa]

09ca958

성공(5m)

카테고리

배열, 비트 연산자

접근

1. 주어진 배열을 탐색하면서 맵에 저장 (주어진값 - 개수)
2. 맵을 전체 탐색하며 값이 1인 경우 키 반환

분석

O(N)

회고

세부 조건으로 공간 복잡도 O(1)을 만족해야 하는 문제

맵을 사용한 최초 풀이의 공간복잡도는 O(N)으로 비트 연산자를 활용하여 해결 가능

• 아이디어
  • 정수는 32비트로 이루어져있고, 숫자들이 3번씩 등장했다면 각 비트 자리의 합도 3의 배수
  • 오직 한 번 등장한 숫자만 비트 자릿수의 합에 나머지 발생
• 접근
  • 각 비트 자리마다 반복문을 통해 확인 (0~31)
  • 해당 비트 자리가 1인 개수 합산
  • 위의 개수를 3으로 나눈 나머지가 0이 아닌 경우, 정답 숫자에 or 연산을 통해 합산
    (정답의 해당 비트 자리를 1로 바꿔줌)