本文共 4256 字，大约阅读时间需要 14 分钟。
题目一：一个数组中，只有一个数字出现了一次，其余都是成对出现，找出这个数字
题目二：一个数组中，有两个数字出现了一次，其余都是成对出现，找出这两个数字 题目三：一个数组中，有三个数字出现了一次，其余都是成对出现，找出这三个数字这三道题目是循序渐进的，典型的用异或求解的问题。
代码比较简单，如下：
#includeint find_one(int *str, int sz) { int ret = 0; for (int i = 0; i < sz; i++) { ret ^= *(str + i); } return ret; } int main() { int arr[] = { 1,2,5,3,11,5,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]); int num1 = 0; int ret = find_one(arr, sz); printf("%d\n", ret); return 0; }
结果：11
第一步：将数组中所有的数字都异或一遍，最终得到的结果记为c，则c=a^b，且 c ≠ 0，
第二步：这就说明c的二进制中一定至少包含一个1，（我们取最低位的1）设 c 的二进制最低位为1的位置为pos， 则，a,b在pos位置上一定一个为0，一个为1，这就找出a和b的不同了， 第三步：我们可以根据数组中所有数字在pos位置的不同来分组，pos位置为0的是一组，是1的是另一组， 这样a和b就被分开了，且分的两个组中其他元素也必成对出现（或为0）， 第四步：将分的两个组进行异或，即可得到a,b代码如下：
#includevoid find_two(int *str, int sz, int *px, int *py) { int ret = 0; int pos = 0; //将所有元素异或 for (int i = 0; i < sz; i++) { ret ^= *(str + i); } //找出pos的位置（下面的代码pos表示右移的位数） for (int i = 0; i < 32; i++) { if (((ret >> i) & 1) == 1) { pos = i; break; } } //根据pos位置的元素来进行分组 for (int i = 0; i < sz; i++) { if (((*(str + i) >> pos) & 1) == 1) { *px ^= *(str + i); } else { *py ^= *(str + i); } } } int main() { int arr[] = { 1,2,5,3,11,5,3,2,1,9 }; int sz = sizeof(arr) / sizeof(arr[0]); int num1 = 0; int num2 = 0; find_two(arr, sz, &num1, &num2); printf("%d %d\n", num1, num2); return 0; }
结果：11 9
注：上述代码中将num1和num2的地址传过去，是为了改变地址中的内容，函数就可以没有返回值了设三个不同的数字为a,b,c
第一步： 将数组所有的元素异或，得到结果ret，则ret = a^b^c，且 ret ≠ 0；
ret^a ≠ 0 ret^b ≠ 0 ret^c ≠ 0，证明： ret^a 实际上就相当于b^c，因为b和c不相等，则ret^a不可能为0 第二步： 写一个函数LastNumberOf1：只保留一个数字二进制的最后一位的1， 其余位为置0 则LastNumberOf1(ret ^ a)、LastNumberOf1(ret ^ b)、LastNumberOf1(ret ^ c)都不为0， 则LastNumberOf1(ret ^ a) ^ LastNumberOf1(ret ^ b) ^ LastNumberOf1(ret ^ c) ≠ 0 第三步： 令N=LastNumberOf1(ret ^ a) ^ LastNumberOf1(ret ^ b) ^ LastNumberOf1(ret ^ c),设N最后一位为1的位置为pos 则在第pos位，LastNumberOf1(ret ^ a)、LastNumberOf1(ret^b)、LastNumberOf1(ret^c)一个为1,或者三个为1 如果三个都为1，那就说明ret在pos位一定与a,b,c在pos位的数字不同，且a,b,c在pos位置的数字一定相同 若a,b,c在pos位置都为0，0^0^0 = 0，矛盾 若a,b,c在pos位置都为1，1^1^1 = 1，矛盾 所有LastNumberOf1(ret ^ a)、LastNumberOf1(ret ^ b)、LastNumberOf1(ret ^ c)在pos位只有一个为1 第四步： 这就找到了一个数字与另外两个数字的不同，LastNumberOf1(arr[i] ^ ret) 的最后一位1出现在第pos位的数中， 只有一个是单独出现的，其余成对出现 ，就能找出其中一个数 第五步：当找出其中一个数字，只需在你创建一个数组，并将之前数组的内容都赋值进去，最后再加上之前找到的数字， 这个问题就又转换为找一个数组中两个不同的数代码如下：
#includeint lastBitOf1(int num) { return num & ~(num - 1); } void find_three(int *str, int sz, int *px, int *py, int *pz) { int ret = 0; int pos = 0; int arr1[12] = { 0 }; int flag = 0; for (int i = 0; i < sz; i++) { ret ^= *(str + i); arr1[i] = *(str + i); } for (int i = 0; i < sz; i++) { flag ^= lastBitOf1(ret ^ *(str + i)); } for (int i = 0; i < sz; i++) { if (lastBitOf1(*(str + i) ^ ret) == flag) *px ^= *(str + i); } arr1[sz] = *px; ret ^= *px; for (int i = 0; i < 32; i++) { if (((ret >> i) & 1) == 1) { pos = i; break; } } for (int i = 0; i < sz + 1; i++) { if (((arr1[i] >> pos) & 1) == 1) { *py ^= arr1[i]; } else { *pz ^= arr1[i]; } } } int main() { int arr[] = { 1,2,5,3,11,10,5,3,2,1,9 }; int sz = sizeof(arr) / sizeof(arr[0]); int num1 = 0; int num2 = 0; int num3 = 0; find_three(arr, sz, &num1, &num2, &num3); printf("%d %d %d\n", num1, num2, num3); return 0; }
结果：10 11 9
转载地址：http://xbwdb.baihongyu.com/