136. 한 번 밖 에 안 나 오 는 숫자

987 단어
빈 정수 가 아 닌 배열 을 지정 합 니 다. 특정한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
설명:
너의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 한다.당신 은 추가 공간 을 사용 하지 않 고 실현 할 수 있 습 니까?
예시 1:
입력: [2, 2, 1] 출력: 1
예시 2:
입력: [4, 1, 2, 1, 2] 출력: 4
사고의 방향
비 할 바 없 이 고전적 인 문 제 였 지만 어디서 본 경전 문 제 는 생각 나 지 않 았 다.고전 문 제 를 설명 합 니 다. n 개 수 에서 모든 숫자 는 짝수 번 이 나타 나 고 특정한 숫자 만 홀수 번 이 나타 나 면 다른 것 으로 판단 합 니 다. a ^ a = 0, 0 ^ b = b 이기 때문에 모든 쌍 을 이 루 는 수 는 0 과 같 습 니 다. 그러면 결국은 홀수 번 의 숫자 만 남 았 습 니 다. 마음대로 예 를 들 어 보 세 요.
0 — 0000 1001 0101
1 — 0000 1100 0000
2 — 0000 1100 0000
    0   1     ，   
x — 0000 0101 0101
    2     ，   
y — 0000 1001 0101，        0

성능 분석
결 과 를 한 번 훑 어보 면 시간 복잡 도 O (N), 공간 복잡 도 O (1)
구체 코드
int singleNumber(vector& nums) {
    int res = 0;  //    
    for(int i = 0; i < nums.size(); i++){ //      
        res ^= nums[i]; //        
    }
    return res;
}
14장. 쓰레드 동기화 기법 2
사과 나 누 기 알고리즘

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage