配列に1回しか現れない問題(異種または問題)

3099 ワード

  • 具体的には、1つの整数配列では、配列はペアで現れ、2つの要素だけが個別の要素であり、この2つの要素の値を求める.
  • 構想:1、ここでは異または予算符の古典的な問題であり、2つの同じ値の異または演算後の値は0である.2、まず配列のすべての要素を異或演算し、最後に2つの単独要素の異或後の値を得た(同じ要素の異或後の値はいずれも0になるため).3、2つの個別要素は必ず1つまたは複数のビットが異なるので、0または1を見つけることができます.このビットが0または1であることによって、配列要素を2つの部分に分けることができます.2つの部分には、それぞれ1つの個別要素があり、もう少し演算すると、この2つの値が見つかります.
  • コード記述
  • #include 
    
    void FindNumsAppearOnce(int (&a)[6])
    {
    //              ,        ,                 
    
        int value = 0;   
        int num1,num2;   //            
        int flag = 1;    //  flag             
        for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
        {
            value ^= a[i];      
        }
        num1 = num2 = value;    //               
        while ((value & flag) == 0)
        {
            flag <<= 1;         //  1,1              
        }
        for (int j = 0; j < sizeof(a) / sizeof(a[0]); j++)
        {
            if ((flag & a[j]) == 0)    
            {
                num1 ^= a[j];
            }
            else {
                num2 ^= a[j];
            }
        }
    
        std::cout << "           :" << "
    "
    << "num1 = " <" num2 = "<< num2; } int main(void) { int a[6] = { 2,4,5,2,5,6 }; FindNumsAppearOnce(a); getchar(); return 0; }
  • 後記この問題はアルゴリズムのテーマを見て、ここで記録して、後で学習を見るために準備します.