2018 년 LeetCode 고주파 알고리즘 면접 문제 풀이 노트 - 한 번 만 나 오 는 숫자 (시작 전)

1. 해답 하기 전의 깨 진 생각:
이 시 리 즈 는 일자 리 를 찾기 전에 내 가 보 여 준 것 이다. 왜냐하면 기억력 이 매우 나 쁜 사람 으로서 시간 이 지나 면 어떻게 쓰 는 지 잊 어 버 릴 것 이다.그리고 애 피타 이 저 첫 번 째 문제 로 생각 이 없어 서 정말 좌절 감 을 느 꼈 어 요...
2. 문제 설명:
빈 정수 가 아 닌 배열 을 지정 합 니 다. 특정한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
설명:
너의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 한다.당신 은 추가 공간 을 사용 하지 않 고 실현 할 수 있 습 니까?
예시 1:

  : [2,2,1]
  : 1

예시 2:

  : [4,1,2,1,2]
  : 4

3. 문제 풀이 방향:
문제 풀이 방향 은 이 링크 에서 유래 합 니 다:https://cuijiahua.com/blog/2018/01/basis_40.html
다음은 유용 한 내용 의 발췌 문 이다.
여러분 이 먼저 생각 하 는 것 은 순서 스 캔 법 이지 만 이런 방법의 시간 복잡 도 는 O (n ^ 2) 입 니 다.이 어 해시 표 의 방법 을 고려 하 겠 지만 공간 복잡 도 는 O (1) 가 아니다.
어떻게 해 야 시간 복잡 도가 O (n) 이 고 공간 복잡 도가 O (1) 라 는 요 구 를 만족 시 킬 수 있 습 니까?
우 리 는 '이 또는' 연산 의 한 성질 을 생각해 볼 수 있 으 며, 우 리 는 직접 예 를 들 어 설명 할 수 있다.
예: {2, 4, 3, 6, 3, 2, 5, 5}
이 배열 에 한 번 밖 에 나타 나 지 않 는 두 개의 수 는 각각 4 와 6 이다.이 두 개의 숫자 를 어떻게 찾 습 니까?
우 리 는 먼저 두 개의 상황 을 보지 않 고 이런 문 제 를 먼저 본다. 어떻게 한 배열 에서 한 번 만 나타 나 는 숫자 를 찾 을 수 있 을 까?예 를 들 어 배열: {4, 5, 5}, 유일 하 게 한 번 만 나타 나 는 숫자 는 4 이다.
우 리 는 어떤 숫자 가 다 르 거나 그 자신 이 0 과 같다 는 것 을 안다.즉, 우리 가 처음부터 끝까지 다른 숫자 나 배열 의 모든 숫자 를 순서대로 한다 면 최종 결 과 는 딱 한 번 만 나 오 는 숫자 라 는 것 이다.예 를 들 어 배열 {4, 5, 5}, 우 리 는 먼저 배열 의 첫 번 째 요소 4 (이 진 형식: 0100) 와 배열 의 두 번 째 요소 5 (이 진 형식: 0101) 로 이 또는 조작 을 하고 0100 과 0101 이 또는 0001 을 얻 으 며 이 로 얻 은 요소 와 배열 의 세 번 째 요소 5 (이 진 형식: 0101) 로 이 또는 조작 을 하고 0001 과 0101 이 또는 0100 을 얻 습 니 다.마침 결과 숫자 4 입 니 다.이 는 배열 에서 같은 원소 가 다 르 거나 0 이기 때문에 쌍 이 되 지 않 는 외 로 운 원소 만 남 았 기 때문이다.
4. 관련 지식:
비트 연산 소결 (비트 와, 비트 또는, 비트 에 따라 다 르 거나, 반대로, 왼쪽으로 이동, 오른쪽으로 이동):https://blog.csdn.net/mengzhengjie/article/details/80611422
발췌:
비트 단위 이동 또는 (^)
   연산 에 참가 한 두 개의 수 를 2 진법 (0, 1) 으로 환산 한 후 이 또는 연산 을 한다.해당 비트 의 숫자 가 같 지 않 을 때 만 1 을 취하 고 같 으 면 0 이다.
1 2 3 4 5 6 10 -10 (^) ： 0000 0000 0000 1010 1111 1111 1111 0110 ----------------------- 1111 1111 1111 1100 ：10 ^ -10 = 1111 1111 1111 1100
   어떤 수 와 0 의 차이 나 결 과 는 그 자체 임 을 알 수 있다.이 를 이용 하거나 좋 은 교환 알고리즘 을 실현 할 수 있 습 니 다. 두 개의 수 를 교환 하 는 데 사 용 됩 니 다. 알고리즘 은 다음 과 같 습 니 다.
1 2 3 a = a ^ b; b = b ^ a; a = a ^ b;
 
5. 답:

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