數組中數字出現的次數

來自專欄基礎演算法筆記

數組中數字出現的次數

題目1：數組中只出現1次的2個數字。

一個整形數組中除2個數字之外，其他數字都出現了2次。請找出這2個數字。

思路：任何一個數字異或它自己都等於0。如果異或整個數組，得到的結果就是數組中唯一出現一次的數字。根據這個思路，我們可以將本題的數組拆分成2個。

數組B:2個相同數字+唯一出現1次的另一個數字。

參考代碼：

root@gt:/home/git/Code# ./a.out _2jin:2 find1index:1 data:1->1data:2->0 data:1->1 data:3->1 data:1->1 data:1->1data:2->0data:2->06 4root@gt:/home/git/Code# cat find2.c #include <stdio.h>int find1index(int _2jin){ int res = 0; int num = _2jin; while((num & 1) == 0) { ++res; num = num >> 1; } printf("_2jin:%d find1index:%d
",_2jin,res); return res;}int isbit1(int data,int index){ int res = 0; data = data >> index; if(data & 1 != 0) { res = 1; printf(" data:%d->%d
",data,res); } else printf("data:%d->%d
",data,res); return res;}void find2(int* pdata,int len,int* num1,int* num2){ if(pdata == NULL || len <= 0) return; int _2jin = 0; for(int i = 0;i < len;++i) _2jin ^= pdata[i]; int index = find1index(_2jin); *num1 = *num2 = 0; for(int i = 0;i < len;++i) { if(isbit1(pdata[i],index)) *num1 ^= pdata[i]; else *num2 ^= pdata[i]; }}int main(){ int pdata[] = {2,4,3,6,3,2,5,5}; int num1; int num2; find2(pdata,sizeof(pdata)/sizeof(int),&num1,&num2); printf("%d %d
",num1,num2); return 0;}

題目2：數組中唯一出現1次的數字。

在一個數組中除了一個數字出現1次，其他數字都出現3次。

思路：我們把數組中所有數字的二進位表示的的每一位加起來，如果某一位的和能被3整除，那麼那個只出現1次的數字的二進位表示中該位為0.

參考代碼：

root@gt:/home/git/Code# ./a.out 0 i:0 temp = 11 i:1 temp = 21 i:2 temp = 40 i:3 temp = 80 i:4 temp = 160 i:5 temp = 320 i:6 temp = 640 i:7 temp = 1280 i:8 temp = 2560 i:9 temp = 5120 i:10 temp = 10240 i:11 temp = 20480 i:12 temp = 40960 i:13 temp = 81920 i:14 temp = 163840 i:15 temp = 327680 i:16 temp = 655360 i:17 temp = 1310720 i:18 temp = 2621440 i:19 temp = 5242880 i:20 temp = 10485760 i:21 temp = 20971520 i:22 temp = 41943040 i:23 temp = 83886080 i:24 temp = 167772160 i:25 temp = 335544320 i:26 temp = 671088640 i:27 temp = 1342177280 i:28 temp = 2684354560 i:29 temp = 5368709120 i:30 temp = 10737418240 i:31 temp = -21474836486root@gt:/home/git/Code# cat find1.c #include <stdio.h>int find1(int* num,int len){ if(num == NULL || len <= 0) return 0; int bitSum[32] = {0}; for(int i = 0;i < len;++i) { int bitMask = 1; for(int j = 0;j < 32;++j) { int bit = num[i] & bitMask; if(bit != 0) ++bitSum[j]; bitMask = bitMask << 1; } } unsigned int res = 0; unsigned int temp = 0; for(int i = 0;i < 32;++i) { printf("%d ",bitSum[i] % 3); temp = (unsigned int)1 << i; printf("i:%d temp = %d
",i,temp); if(bitSum[i] % 3 != 0) res += temp; } return res;}int main(){ int num[] = {1,1,2,2,3,3,4,4,5,5,6,5,4,3,2,1}; int res = find1(num,sizeof(num)/sizeof(int)); printf("
%d
",res); return 0;}

推薦閱讀：