[LeetCode] 137. Single Number II

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

Single Number II - LeetCode

문제 유형 : 배열 / 비트마스크

문제 난이도 : Medium

 

문제

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

배열에 단 하나의 숫자만 한 번 나오고, 나머지는 두 번 나옵니다.

 

풀이

ones와 twos는 각 비트 위치를 3으로 나눈 값들을 저장하기 위한 변수입니다.

xor연산을 통해서 비트값의 중복을 상쇄시킬 수 있습니다.

ones에는 한 번만 나온 값이 저장되고,

twos에 두 번만 나온 값이 저장될 때, ones는 0으로 초기화됩니다.

같은 숫자가 세 번 나오면, ones와 twos모두 0으로 초기화됩니다.

한 번만 나온 숫자를 제외하고, 모두 상쇄되어 없어집니다.

 

코드(C++)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0;
        int twos = 0;

        for(auto n : nums){
            ones = (~twos) & (ones ^ n);
            twos = (~ones) & (twos ^ n);
        }
        return ones;
    }
};