剣指offer――配列に一度しか現れない数字

タイトルの説明
1つの整数配列には2つの数字を除いて偶数回の数字が現れた.プログラムを書いて、この2つの一度しか現れない数字を見つけてください.
2つの方法、1つは簡単で、1つは筋肉をショーします.
1つ目のコードは次のようにcount関数を使用します.

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len = data.size();
        int flag=1;
        for(int i=0;iint num=count(data.begin(),data.end(),data[i]);
            if(num%2==0)
                continue;
            if(num%2!=0&&flag==1){
                *num1=data[i];
                flag++;
            }
            else if(num%2!=0&&flag==2){
                *num2=data[i];
            }
        }
    }
};

第二の思想も難しくなく、異或を使う.
まず、この問題の簡単なバージョンを考えてみましょう.1つの配列には1つの数字を除いて、他の数字が2回現れています.プログラムを書いて一度しか現れない数字を見つけてください.このテーマの突破口はどこですか.テーマはどうして1つの数字が1回、他の数字が2回現れることを強調しますか?異或演算の性質を考えた:いずれの数字も異或はそれ自体が0に等しい.つまり、もし私たちが最初から最後まで順番に配列の中のすべての数字を異ならせたら、最終的な結果はちょうど1回しか現れない数字です.2回現れた数字はすべて異或で相殺されたからです.上記の簡単な問題の解決策があった後、私たちは元の問題に戻ります.元の配列を2つのサブ配列に分けることができれば.各サブ配列には、1回のみ表示される数値が含まれ、他の数値は2回表示されます.このように元の配列を分割することができれば,前の方法では,この2つの1回しか現れない数字をそれぞれ求めることになる.私たちはやはり最初から最後まで順番に配列の中のすべての数字を異にして、最終的に得た結果は2つの1回しか現れない数字の異種または結果です.他の数字は2回も現れたので、異或ではすべて相殺された.この2つの数字は異なるに違いないので、この異或結果は0ではないに違いない.つまり、この結果の数字のバイナリ表現には少なくとも1人が1である.結果数字で1番目のビットの位置を見つけ,N番目のビットと記す.ここでは、N番目のサブ配列が1であるか否かを基準に、元の配列の数字を2つのサブ配列に分け、1番目のサブ配列の各数字のN番目のビットは1であり、2番目のサブ配列の各数字のN番目のビットは0である.元の配列を2つのサブ配列に分け、各サブ配列には1回しか現れない数字が含まれており、他の数字は2回現れています.だからここまで、私たちはすべての問題を解決しました.

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2)
            return ;
        int size=data.size();
        int temp=data[0];
        for(int i=1;iif(temp==0)
            return ;
        int index=0;
        while((temp&1)==0){
            temp=temp>>1;
            ++index;
        }
        *num1=*num2=0;
        for(int i=0;iif(IsBit(data[i],index))
                *num1^=data[i];
           else
                *num2^=data[i];
        }
    }
    bool IsBit(int num,int index)
    {
        num=num>>index;
        return (num&1);
    }
};