C++LeetCode 구현(136.단독 숫자)

[LeetCode]136.single Number 단독 숫자
Given a non-empty array of integers, every element appears twice except for one. 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,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
이 문 제 는 우리 에 게 비 어 있 는 정수 배열 을 주 었 다.한 숫자 를 제외 한 모든 숫자 가 마침 두 번 이나 나 타 났 다 고 해서 우 리 는 이 한 번 만 나 오 는 숫자 를 찾 아 냈 다.문제 에서 우 리 는 선형 시간 복잡 도 에서 해 를 구 할 수 있다.그러면 매우 직접적인 사 고 는 바로 HashSet 을 사용 하여 상수 급 의 검색 속 도 를 이용 하 는 것 이다.배열 의 모든 숫자 를 옮 겨 다 니 며 현재 숫자 가 HashSet 에 있 으 면 HashSet 의 이 숫자 를 제거 합 니 다.그렇지 않 으 면 HashSet 에 가입 합 니 다.이것 은 두 번 상쇄 하 는 것 과 같 습 니 다.결국 모든 일 에 두 번 발생 하 는 숫자 는 모두 HashSet 에서 제거 되 었 습 니 다.유일 하 게 남 은 것 은 단독 숫자 입 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> st;
        for (int num : nums) {
            if (st.count(num)) st.erase(num);
            else st.insert(num);
        }
        return *st.begin();
    }
};

자바 해법 1:

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            if (!st.add(num)) st.remove(num);
        }
        return st.iterator().next();
    }
}

문제 에서 우 리 는 추가 공간 을 사용 하지 않 고 하 라 고 했다.원래는 매우 간단 한 문제 이지 만 시간 복잡 도 는 반드시 O(n)이 어야 하고 공간 복잡 도 는 O(1)이기 때문에 정렬 방법 을 사용 할 수 없고 HashSet 데이터 구 조 를 사용 할 수 없다.그러면 다른 길 을 개척 할 수 밖 에 없다.비트 조작 Bit Operation 으로 이 문 제 를 풀 어야 한다.이 해법 은 내 가 생각 하 게 되면 생각 이 나 지 않 을 것 이다.왜냐하면 누가 논리 적 으로 다른 것 으로 문 제 를 풀 생각 을 하 겠 는가?논리 가 다 르 거나 진 값 표 는 다음 과 같 습 니 다.
 이 또는 연산 의 진가 표 는 다음 과 같다.
A
B
F
F
F
F
T
T
T
F
T
T
T
F
숫자 는 컴퓨터 에 바 이 너 리 로 저장 되 어 있 기 때문에 모든 비트 에 0 또는 1 입 니 다.만약 에 우리 가 똑 같은 숫자 를 0 과 0 으로 바 꾸 면... '혹은 0,1 과 1 입 니 다. '혹은 하 긴 0.그러면 우 리 는 0 을 얻 을 수 있다.이 특징 에 따라 우 리 는 배열 의 모든 숫자 를 '혹은 일어나 면 같은 숫자 한 쌍 에 0 을 얻 고 마지막 에 남 은 숫자 는 한 번 밖 에 없 는 숫자 다.이 방법 은 정말 훌륭 합 니 다.하지만 일반인 들 은'이상 하거나'에 대해 생각 하지 않 을 것 같 습 니 다.CS 학과 학생 들 을 위 한 좋 은 문제 입 니 다.짠! 
C++해법 2:

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

자바 해법 2:

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

C++구현 LeetCode(136.단독 숫자)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 단독 디지털 콘 텐 츠 는 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!