配列内に存在する数値をビットワイズ演算子を使用して1回だけ検索する

Question

配列が2つ存在し、1回だけ出現する配列を持つ場合、XOR演算子を使用して、法律。例えば

1 2 3 2 3 
1^2^3^2^3 = (2^2)^(3^3)^1 = 1 

しかし、我々は他の数字がn回occureことができるときに一度配列にoccures数、nは> 1を見つけるために、ビット単位のトリックを使用することができますか？

Answer 1

ビット単位の演算子を使用すると、nが常に偶数でない場合を除きます。

しかし、一度発生するアイテムのソートアンドスキャンや、入力ドメインが何らかの理由で制限されている場合、各アイテムをバケットに割り当てるなど、使用できる方法はたくさんあります。最初の例として

：

def findASingle(list): 
    if list length is zero: 
     return nothing 
    if list length is one: 
     return first item in list 
    sort list 
    for each item in last other than first and last: 
     if item is different to both previous and next item: 
      return item 

そして、第二のために、それは（例えば）一桁非負整数に制限だと仮定すると：

def findASingle(list): 
    create count[0..9], all set to zero 
    for each item in last: 
     count[item] = count[item] + 1 
    for each index 0 through 9 inclusive: 
     if count[index] is 1: 
      return index 
    return nothing 

Answer 2

方法がありますバイナリ演算子ではできません。各数値をビットのベクトルとして表示し、sum（mod n）を使ってすべてのベクトルを合計します。結果のベクトルは、その一意の数を表します。

例えば

、の考えるN = 3及び配列2 3 5 2 5 2

ベクトルである：[0 1 0]、[0 1 1]、[1 0 1]、[0 1 0]、[1 0 1]、[1 0 1]、[0 1 0]

要素毎の和の全てのベクトルは：

Mod 3であり、[0 1 1]は、配列中の3つの固有の要素に相当する。

これはXORトリックの一般化です。実際にはXORは正確にこの操作です - モジュレーション2での集計。