今天看到一個算法題蕾管，感覺應(yīng)該很簡單就能搞定螃诅，但是想了很久還是沒想到啡氢，囧。最后還是網(wǎng)上查了別人的解法术裸，跟大家分享一下：
題目：
給定一個數(shù)組倘是，除了一個數(shù)出現(xiàn)1次之外，其余數(shù)都出現(xiàn)3次袭艺。找出出現(xiàn)一次的數(shù)搀崭。
如：{1, 2, 1, 2, 1, 2, 7}, 找出7.
格式：第一行輸入一個數(shù)n，代表數(shù)組的長度猾编，接下來一行輸入數(shù)組A[n],(輸入的數(shù)組必須滿足問題描述的要求),最后輸出只出現(xiàn)一次的數(shù)瘤睹。
要求：你的算法只能是線性時間的復(fù)雜度，并且不能使用額外的空間哦～
思路：
首先這題很容易聯(lián)想到另外一題答倡，也是找出單獨(dú)的數(shù)轰传，不同的是，另外一題中其他數(shù)都是出現(xiàn)2次瘪撇，所以使用異或運(yùn)算后获茬，對于二進(jìn)制每一位，相同的數(shù)就被消除了倔既，得到了單獨(dú)的數(shù)字恕曲。但是，這題中其他數(shù)字是出現(xiàn)3次的渤涌。不過我們還是可以從前面的解法得到啟發(fā)佩谣，使用二進(jìn)制的位運(yùn)算，既然其他每次數(shù)都出現(xiàn)3次歼捏，那么如果針對每一位求和并對3取余稿存，那么那些出現(xiàn)3次的數(shù)字在這一位的和對3取余后肯定是0笨篷，其實(shí)就是單獨(dú)的那個數(shù)在這一位上的結(jié)果。所以瓣履，針對32位的整數(shù)率翅，我們只要求出二進(jìn)制的每一位的和對3取余，就是單獨(dú)的數(shù)的二進(jìn)制袖迎，再轉(zhuǎn)化成10進(jìn)制冕臭，就是我們需要的答案。
示意圖：
代碼：
#include<stdio.h>
int main(){
int sum[32], n, a;
for(int i=0; i<32; i++){
sum[i] = 0;
}
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a);
for(int j=0; j<32; j++){
sum[j]+=a>>j&1;
sum[j]%=3;
}
}
int ans = 0;
for(int i=0; i<32; i++){
ans += sum[i]<<i;
}
printf("%d\n", ans);
}
