一個全是數字的大數組，除了其中一個數字出現2次外，其餘的數字都出現了3次。如何找出那個只出現了兩次的數字？

01-21

將數字表示成３進位, 數組第 i 個數 3^j 位計為 x(i, j), x(i, j) = 0, 1, 或者 2.

2 * sum(x(i, 0), i = 0, 1, ...) mod 3 即為所求數3進位下第一位, 同理求第二位, 第三位, 等.

int A = 0, B = 0; for (int i = 0; i &< 3 * N + 2; i++) { A ^= P[i] ~B; B ^= P[i] ~A; }

多說一句，我覺得這道題作為面試題並不好，因為面試者很可能見過這個題目，那就沒有意義了。

而且面試結果並不取決於你是否能給出答案，而在於你思考的過程。如果你聽到問題直接給出上面的答案，反倒不會獲得加分。

開個32的數組用求余模擬異或，每個數的所有bit加到每一位上，最後所有結果mod3

來源：http://blog.renren.com/share/301819099/6592584732/

ones = twos = 0

for each x in list {

twos

= ones x

ones ^= x

not_threes = ~(ones twos)

ones = not_threes

twos = not_threes

}

return ones;

其中ones記錄了所有出現了模3餘1次的bit，twos記錄的是餘2的。not_threes是當一個bit出現第3次的時候，把它清掉。

最後輸出ones（如果題目中那個特殊的數出現了1次，當然如果是出現2次的話，應該輸出twos。）

First of all, we can use hash map, the panacea solution. It takes O(n) time complexity and O(n) memory.

If you want to reduce the memory usage, bit map is a good alternative.

And there is a better solution which takes only O(1) memory complexity and O(n) time.

Allocate a new array S[] of length 32 (64 if you use the long long), then count the number of 1s for each bit position. And every i that S[i] % 3 == 2 indicate that the "twice number" has a "1" at ith bit position.

The ultimate solution is like this.

nums = map(int, raw_input().split())


(one, two) = (0, 0)

for num in nums:

    one = (one ^ num)  ~two

    two = (two ^ num)  ~one

print two

# INSPIRED BY: https://oj.leetcode.com/discuss/6632/challenge-me-thx

You can think about it.

同意蔣長生的三進位方法，很巧妙。之前在BOJ上做過一道題，用的二進位方式，將所有數保存成二進位形式，統計所有3N-1個數中對應位置的二進位之和m，取m%3，if(m%3==0)，則結果該位為0，if(m%3==2)，則結果該位為1。

如果事先知道這些數所組成的集合S,可以把S中所有元素異或的結果記為x1,把該數組的所有數字異或

結果記為x2,那麼x1^x2就是出現2次的那個數。但是知道S這個條件太苛刻了。

我認為轉換成2進位或3進位還不如直接統計。