137. Single Number II

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

Single Number II - LeetCode

난이도 : medium

문제

배열에서 원소가 하나인 원소를 출력하라. 딱 하나를 제외하고 나머지는 3번나온다.

 

코드

map 자료형에 키값으로 원소를 넣고 value 로 카운트 한다.

count != 가 아닌 원소를 출력 한다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        
        // 3개 나오면 skip
        // 하나 인것만 출력
        // 오직 하나만
        unordered_map<int, int> m;
        for(auto a:nums) {
            m[a]++;
        }
        
        for(auto a:m){
            if(a.second != 3) {
                return a.first;
            }
        }
        
        return -1;
    }
};

 

해당문제는 비트연산을 이용하여서 푸는 문제라고 한다.

입력을 [2,2,2,3] 으로 설정합니다. 입력을 통해 수직으로 32번 반복합니다(정수는 32비트로 표시됨)
2-> 1 0
2-> 1 0
2-> 1 0
3-> 1 1

각 i번째 수직 레벨의 합을 찾습니다. (i 범위 0 ~ 31)

합계가 3으로 나눌 수 있는 경우 단일 발생 숫자의 i번째 비트는 0입니다(1을 제외한 각 숫자는 세 번 발생하므로 비트합은 3(일부 상수) 합이 3으로 나눌 수 없는 경우 단일 발생 숫자의 i번째 비트는 1입니다(이 경우 비트합은 3(상수) +1이 되기 때문에 i번째 비트는 발생하는 단일 숫자에 설정되기 때문에 i번째 비트의 합이 3으로 나누어 떨어지지 않을 때 i번째 비트를 설정하여 숫자를 생성 해야 합니다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int bitSum = 0;
            for(int num:nums){
                bitSum += (( num >> i ) & 1);
            }
            if(bitSum % 3){
                ans = ans |( 1 << i);
            }
        }
        return ans;
    }
};