algorithm - 一度出現する要素を見つける

Question

一度出現する要素を見つける

1 回だけ出現する 1 つの要素を除いて、すべての要素が 3 回出現する配列が与えられます。1 回出現する要素を見つけます。

予想される時間の複雑さは、O(n) および O(1) の余分なスペースです。

例:

入力: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

出力: 2

Answer 1

O(1) スペースの制約がなければ、値が出現回数であるハッシュマップを使用できたはずです。

int getUniqueElement(int[] arr)
{
    int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once.
    int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice.
    int not_threes ;

    for( int x : arr )
    {
        twos |= ones & x ; //add it to twos if it exists in ones
        ones ^= x ; //if it exists in ones, remove it, otherwise, add it

        // Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero.

        not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes.
        ones &= not_threes ;//remove x from ones
        twos &= not_threes ;//remove x from twos
    } 
    return ones;
}

基本的に、それは と という事実を利用しx^x = 0ます0^x=x。したがって、ペアになっているすべての要素が XOR され、孤独な要素を残して消えます。

要するに ：

ビットがすでに 1 になっている場合は、2 に追加します。

XOR は、このビットが存在しない場合は 1 に追加し、既に存在する場合はこのビットを 1 から削除します。

ビットが 1 と 2 の両方にある場合は、1 と 2 から削除します。

終了すると、ones には 3*n+1 回だけ出現したビットが含まれます。これは、1 回だけ出現した要素のビットです。

Answer 2

hereで説明されているように、配列の要素の中央値は、最悪の場合の O(n) 時間と O(1) 余分なスペースで見つけることができます。したがって、分割統治法で問題を解決できます。

O(n) 時間で中央値を見つけ、O(n) で中央値以下の要素の数を数えます。この数が 3k+1 の場合、答えが中央値以下であることを意味するので、O(n) で中央値より大きい要素を省略します。そうでない場合は、中央値以下のものを省略します。次に、T(n/2) の残りの要素で答えを再帰的に見つけます。注: 要素の半分を省略したため、残りの要素の数は n/2 です。

したがって、T(n) = T(n/2)+O(n) = O(n) となり、O(1) 余分なスペースが必要になります。

Answer 3

私はmhsekhavatによって提案されたものと同様の解決策を提案します。中央値を決定する代わりに、オランダの国家旗問題http://en.wikipedia.org/wiki/Dutch_national_flag_problemの分割アルゴリズムを使用することを提案します（はい、私はオランダ人であり、ダイクストラのスタイルで教育を受けました）。

アルゴリズムを適用した結果、配列は赤、白、青の部分に分割されます。白い部分はピボットと見なすことができます。白い部分はピボットに等しいすべての要素で構成されているため、白い部分は1つまたは3つの要素で構成されていることに注意してください。赤い部分はピボットよりも小さい要素で構成され、青い部分はピボットよりも大きい要素で構成されています。（赤と青の部分はソートされていないことに注意してください！）

次に、赤、白、青の部分の要素の数を数えます。いずれかの部分が1つの要素で構成されている場合、それが探している番号です。それ以外の場合、赤または青の部分は、指定された数のkに対して3k+1個の要素で構成されます。3k+1要素で構成される部分でアルゴリズムを繰り返します。最終的に、パーツの1つはサイズ1になります。

アルゴリズムはO（n）で実行され、O（1）変数が必要です。

Answer 4

質問はすでに回答されていますが、次のほうがより直感的であるため、回答として追加しました。本来はここから

int singleNumber(vector<int>& nums) {
    /*Bits in 'ones' are set to 1, when that particular bit 
      occurs for the first time. Bits in 'twos' are set to 1, 
      when that particular bit occurs for the second time. If a 
      bit is occurring for more than 2 times, we throw it away 
      and start counting again.*/
    int ones = 0;
    int twos = 0;
    for (auto elem : nums) {
        int onesOld = ones;
        /* (ones ^ elem): consider the ith bit in 'ones' be 0 (i.e. ith 
           bit has not occurred till now or has occurred 2 times) and in 
           'elem' be 1. So, for the ith bit (ones ^ elem) gives 1. Now,
           ith bit could have occurred even number of times as well (i.e. 
           ith bit in twos is set to 1). If that was the case, we 
           would like to ignore such bit. This last part is taken care 
           of by '&' with '~twos' 
           */
        ones = (ones ^ elem) & ~twos;
        /* (onesOld & elem) gives the bits which have occurred ones 
           and also occur in this particular element. (twos & ~elem) 
           gives the bits that have occurred twice and do not occur 
           in this element. Both these cases take care of the bits 
           that have occurred 2 times (although a bit might be set 
           more than 2 times, like 5,7... but we take only modulo 3 
           count).
        */
        twos = (onesOld & elem) | (twos & ~elem);
    }
    return ones;
}