整数の配列では、1つの数字が2回現れる以外は3回現れますが、2回現れる数字を探します。

Question

これは、「プログラミングのインタビューの要素」から問題があります。私はこの問題がhereと掲載されているのを見ましたが、受け入れられた回答（または他の回答）は完全ではありません。

ベース3のシステム（ポストのxor3と呼ばれる）で動作するXORのような操作を使用すると、結果はx xor3 xになります。しかし、問題はxです。 xor3は、モジュロ3の加算として定義されます（数字はベース3のシステムで表されます）

部分をx xor3 xからどのように取得しますか？

Answer 1

数値の配列をもう一度見直すとどうなりますか？最初の反復後の値はa = x xor3 x

であり、配列内のすべてのエントリを反復し、各値はaでxor3です。

for y in arr: 
    if y xor3 a == 0: 
     print y 
     break 
    else 
     continue 

今のところ私はこれがナイーブな解決策だと考えています。これはO（1）とO（1）としてそれぞれxor3を考えると、まだO（n）です。