http://blog.csdn.net/Dinosoft/article/details/6443354

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

一個全是32位整數的大數組，除了其中一個數字出現1次外，其余的數字都出現了3次。如何找出那個只出現了1次的數字？

考慮數組元素的某一個位，即bit

在這個位上，其他所有數字在這個位上1的數量是3的倍數

如果在這個位上，特殊值為0，則數組所有數字在這個位上的1的數量之和也是3的倍數

如果在這個位上，特殊值為1，則數組所有數字在這個位上的1的數量之和不是3的倍數

由此可以認為，每一個位上均是做三進制的運算，一旦為3，則這個位要清零

則，最后的數即要查找的數

用兩個數組模擬三進制的加法，one表示低位，two表示高位，如果特殊值出現一次，返回one，出現兩次，返回two

int special(int a[], int n) {int one = 0;int two = 0;for (int i = 0; i < n; ++i) {two |= one & a[i];one ^= a[i];int notThree = ~(one & two);one &= notThree;two &= notThree;}return two; }

總結

以上是生活随笔為你收集整理的在重复3次的数组中查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。