C++LeetCode 구현(137.단독 숫자의 2)

[LeetCode]137.Single Number II 단독 숫자 2
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
이 문 제 는 이전 문제 입 니 다Single Number 의 연장 은 그 문제 의 해법 이 비교적 독특 하 다.컴퓨터 가 비트 에 따라 숫자 를 저장 하 는 특성 을 이용 하여 만 든 것 이다.이 문 제 는 하나의 단독 숫자 를 제외 하고 배열 에 있 는 다른 숫자 가 모두 세 번 나 왔 는 지 비트 조작 Bit Manipulation 을 이용 하여 풀 어야 하 는 지 하 는 것 이다.32 자리 숫자 를 만들어 서 한 명 에 1 이 나 오 는 개 수 를 집계 할 수 있 습 니 다.한 명 에 1 이 나 오 면 이 정수 가 세 번,3 에 0 이 나 오 면 각 수의 대응 위 치 를 합 쳐 3 에 나머지 를 얻 고 마지막 에 남 은 그 수 는 하나의 숫자 입 니 다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j) {
                sum += (nums[j] >> i) & 1;
            }
            res |= (sum % 3) << i;
        }
        return res;
    }
};

또 하나의 해법 은 아이디어 가 비슷 하 다.INT 를 3 개의 정수 로 나타 내 는 여러분 의 출현 횟수 상황 을 원 은 1 번,투 는 2 번 나 타 났 다 는 뜻 이다.세 번 나 왔 을 때 이 자 리 는 0 이 었 다.마지막 답 은 원 의 값 이다.

ones   대표 비트 에 한 번 만 나타 나 는 마스크 변수

twos  대표 비트 에 두 번 만 나타 나 는 마스크 변수

threes  대표 비트 에 세 번 만 나타 나 는 마스크 변수

만약 에 현재 하나의 숫자 1 이 있다 고 가정 하면 one 을 업데이트 하 는 방법 은 바로'또는'라 는 1 이 고 one 은 1 이 되 는 것 이다.그리고 two 의 업데이트 방법 은 지난 상태 에서 one 으로'위 숫자 1'을 한 다음 에'또는'이 결 과 를 업데이트 하 는 것 이다.그러면 예전 에 one 이 1 이 었 다 면 이때 two 도 1 이 되 었 을 것 이다.이 make sense 는 현재 위치 에서 두 개의 1 을 만 났 다 는 것 을 설명 하기 때문이다.반대로 이전에 원 이 0 이 었 다 면 지금 은 two 가 0 이다.업데이트 순 서 는 two 를 먼저 업데이트 하고 one 을 업데이트 하 는 것 입 니 다.이해 하지 못 하면 하나의 숫자 1 만 있 는 입력 배열 을 가지 고 보면 이해 하기 어렵 지 않 습 니 다.그리고 three 를 업데이트 합 니 다.만약 에 이때 one 과 two 가 모두 1 이 라면 먼저 업 데 이 트 된 two,다시 업 데 이 트 된 one,two 가 1 이기 때문에 이때 적어도 두 개의 숫자 가 1 이라는 것 을 설명 합 니 다.이때 one 은 1 이라는 것 은 이때 이미 세 개의 숫자 가 있다 는 것 을 설명 합 니 다.이것 은 곰 곰 이 생각해 야 합 니 다.one 은'또는'하나 1 의 값 이 1 이 어야 하기 때문에 이전 one 이 0 이라는 것 을 설명 합 니 다.실제 상황 은...두 번 째 1 이 왔 을 때 two 는 먼저 1 로 업데이트 되 었 습 니 다.이때 one 은 0 으로 업데이트 되 었 습 니 다.아래 three 는 0 입 니 다.그러면't hree 의 반대 수 1 과 one 과 two 의 값 을 바 꾸 지 않 습 니 다.그러면 세 번 째 1 이 왔 을 때 two 또는 1 이 었 습 니 다.이때 one 은 1 로 업데이트 되 었 습 니 다.그러면 three 는 1 로 업데이트 되 었 습 니 다.이때 one 과 two 를 비우 고'위의 three 와 반대 되 는 0 을 세면 됩 니 다.최종 결 과 는 one 에 저 장 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= one & nums[i];
            one ^= nums[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

아래 의 이런 해법 사고방식 도 매우 교묘 하 다.위의 해법 의 사고방식 에 따라 우 리 는 수조 에 있 는 숫자의 한 분 한 분 을 누적 하여 3 에 나머지 를 취한 다.나머지 결 과 는 바로 그 단독 수조 의 이 자리 에 있 는 숫자 이다.누적 하 는 과정 이 모두 3 에 나머지 를 취하 기 때문에 한 분 한 분 이 누적 하 는 과정 은 0->1->2->0 이다.2 진법 으로 바 꾸 면 00->01->10->00 이다.대응 하 는 관 계 를 쓸 수 있 습 니 다:
00 (+) 1 = 01
01 (+) 1 = 10
10 (+) 1 = 00 ( mod 3)
ab 로 시작 상 태 를 표시 합 니 다.1 작업 을 추가 한 후 얻 은 새로운 상태의 ab 알고리즘 은 다음 과 같 습 니 다.
b = b xor r & ~a;
a = a xor r & ~b;
여기 ab 는 바로 위의 세 가지 상태 00,01,10 의 10 비트 와 여러분 입 니 다.처음에 a 와 b 는 모두 0 이 었 습 니 다.이때 숫자 1 을 만 났 을 때 b 는 1 로 업데이트 되 었 고 a 는 0 으로 업데이트 되 었 으 며 바로 01 의 상태 입 니 다.다시 1 을 만 났 을 때 b 는 0 으로 업데이트 되 고 a 는 1 로 업데이트 되 며 10 의 상태 입 니 다.다시 1 을 만 났 을 때 b 는 0 으로 업데이트 되 었 고 a 는 0 으로 업데이트 되 었 으 며 00 의 상태 로 리 셋 된 것 과 같 습 니 다.마지막 결 과 는 b 에 저장 되 어 위의 분석 과정 을 알 게 되면 코드 를 다음 과 같이 쓸 수 있 습 니 다.
해법 3:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); ++i) {
            b = (b ^ nums[i]) & ~a;
            a = (a ^ nums[i]) & ~b;
        }
        return b;
    }
};

C++구현 LeetCode(137.단독 숫자의 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 단독 숫자의 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 읽 어 주시 기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!