[C++]LeetCode: 67 Single Number II

タイトル:
Given an array of integers, every element appears three times except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
3回も現れていない数字を見つけて、同じように線形時間を要求して、余分な空間を使用しません.
Answer 1:1ビットあたりの個数を集計する
考え方:
数字はコンピュータにビットで格納されていることを考慮します.
すべての数字のi番目のビットビットが合計され、モード3である場合、結果は1または0であり、各数字は3回または1回しか現れないため、このi番目のビットビットは「single number」を表すことができ、すなわち、最後のモード3によってsingle numberの各ビットの値が0であるか1であるかを決定することができる.Single Numberとの異曲同工の妙.
複雑度:外層循環統計32ビットのため、複雑度はO(32*N)即ちO(N)である.
Attention:
1.必ず初期化結果を0にし、関数内の内蔵変数値をランダムにします(コンパイラは0に初期化する可能性がありますが、この可能な動作に依存しないでください.プログラムに未定義の動作をもたらす可能性があります).グローバル範囲内の組み込み型変数の場合、コンパイラは自動的に0値に初期化されます.

<span style="font-size:14px;">int ret = 0;</span>

error:

<span style="font-size:14px;">int ret;</span>

1/11 test cases passed.
Status:  Wrong Answer
Submitted: 10 minutes ago
Input:
[1]
Output:
966166951
Expected:
1
 2. どのように1ビットごとに1の個数を統計するかは,d=1を設定し,iビットを移動することで所望の結果を得る必要がある.

<span style="font-size:14px;">int d = 1 << i;  //   i ，     
//   i    
 for(int j = 0; j < n; j++)
{
     if(A[j] & d) c++;   
}
            
 //  i ，1     3    ，      1
 if(c % 3) ret |= d;</span>

AC Code:

<span style="font-size:14px;">class Solution {
public:
    int singleNumber(int A[], int n) {
        int ret = 0;
        
        for(int i = 0; i < 32; i++)
        {
            int c = 0;
            int d = 1 << i;  //   i ，     
            //   i    
            for(int j = 0; j < n; j++)
            {
                if(A[j] & d) c++;   
            }
            
            //  i ，1     3    ，      1
            if(c % 3) ret |= d;
        }
        
        return ret;
    }
};</span>

Answer 2:マスク法
構想:onesはこれまで計算した変数を記録するまで,バイナリ1に「1回」(mod 3は1)の数ビットが現れる.twosは,これまで計算した変数までを記録し,バイナリに「2」回(mod 3は2)の数ビットが現れる.onesとtwosのいずれかが同時に1であることを示すと,バイナリは1が3回出現し,そのビットはクリアされる.3進数計算をバイナリでシミュレートします.最終onesが記録したのは最終結果です.onesはithビットに1回しか現れないマスク変数を表す.twosはithビット目に2回しか現れないマスク変数を表す.threesはithビット目に3回しか現れないマスク変数を表す.
i番目のビットビットが3回目に現れると、クリアonesとtwosのi番目のビットはいずれも0である.最後の答えはonesだ
例:
配列の最初の3つを5にすると、各変数は次のように変化します.
ones = 101, twos = 0, threes = 0;
ones = 0, twos = 101, threes = 0;
ones = 101, twos = 101, threes = 0;(清ones^=A[i])=>ones=0,twos=0,threes=101に実行します.(クリア後まで実行)
Attention:
このビットの操作方法は非常に巧みで,よく学ぶ必要があり,最初は理解しにくいが,シミュレーション三進法から始めると容易であり,各変数は32ビットビットの配列を表す.
AC Code:

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        
        for(int i = 0; i < n; i++)
        {
            twos |= ones & A[i];  //twos   
            ones ^= A[i];  //ones    ，3    1        
            threes = ones & twos; //        ，ones twos        
            ones &= ~threes;  //           
            twos &= ~threes;
        }
        
        return ones;
        
    }
};

別のブログを見ると、この方法の普及応用もあり、考え方を開拓するのに使えます.
leetcode Single Number II-ビット演算処理配列の数
拡張1:
n個の整数を含む配列を与え,1個の数が2回現れる以外はすべての整数が3回現れ,これが2回しか現れない整数を見つけた.onesレコード1に1回出現する数、twosレコード1に2回出現する数は、twosレコードが最終結果であることが分かりやすい.
拡張2:
n個の整数を含む配列が与えられ、1つの整数xがb回、1つの整数yがc回、その他のすべての数がa回であり、bとcはaの倍数ではなく、xとyを見つける.バイナリシミュレーションa進法を用いて、バイナリビット1の出現回数を累積し、回数がaに達したときにゼロにすることで、b mod a次x,c mod a次yの累積を得ることができる.残りの結果(ones、twos、fours...変数で表される)の各バイナリビット1が現れる回数を巡り、回数がb mod aまたはc mod aであれば、xとyの現在のバイナリビットが異なる(1つは0、もう1つは1)ことを説明し、これに基づいてバイナリビットは元の配列を2つのグループに分け、1つのグループは1、もう1つのグループは0である.このような問題は、「1つの整数にa 1回(a 1=bまたはa 1=c)が現れる以外はすべての整数にa回が現れる」ということであり、上記と同様の方法で計算すると最終結果が得られ、シミュレーションa進数計算で使用される変数がones、twos、fours...では最終結果はones|twos|fours...に表示されます.