배열 에 한 번 만 나 오 는 두 개의 숫자 를 찾 아 라.

제목: 하나의 정형 배열 에 두 개의 숫자 를 제외 하고 다른 숫자 는 모두 두 번 나 왔 다.프로그램 을 써 서 이 두 개의 한 번 만 나 오 는 숫자 를 찾 아 보 세 요.요구 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.
아직도 이해 가 안 돼.이 문제 의 주요 사고방식 은 역시 이전의 수조 에서 한 번 만 나타 난 숫자의 그런 모델 로 한 번 에 다른 것 을 덧 붙 이거 나 연산 을 덧 붙 이 는 것 이다.그러면 이 이 또는 의 값 은 틀림없이 이 두 개의 한 번 만 나타 나 는 숫자의 상이 또는 값 일 것 이다.그러면 이 값 의 바 이 너 리 표현 형식 중의 1 의 결 과 는 이 두 숫자 가 이 bit 위치 에서 다르다 는 것 을 나타 낸다.그러면 이 를 통 해 우 리 는 이 bit 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트
이 를 통 해 다른 두 번 의 숫자 가 같은 그룹 으로 나 뉘 었 다 면 결 과 는 두 조 의 데이터 가 있 고 각 조 는 홀수 의 숫자 이 며 한 번 만 나 오 는 숫자 가 있다.
#include<stdio.h>
#include<assert.h>
int findOutTwo(int *a,int n,int &x,int &y){
    assert(a);
    assert(n>2);
    int result=a[0];
    for(int i=1;i<n;++i)
        result^=a[i];
    int b=result&-result;
    x=0;
    y=0;
    for(int i=0;i<n;++i)
    {
        if(b&a[i])
            x^=a[i];
        else
            y^=a[i];
    }
    return 0;
}
int main()
{
    int a[]={1,1,2,2,3,3,4,4,5,6};
    int x,y;
    findOutTwo(a,sizeof(a)/sizeof(int),x,y);
    printf("%d %d
"
,x,y); getchar(); return 0; }

결 과 는:

좋은 웹페이지 즐겨찾기