先看看这个题目：某整形数组中除了两个单身整数外， 其余的整数都是成对出现的， 利用C代码求出这两个单身整数。 要求： 时间复杂度o(n), 空间复杂度o(1).
我们先用最傻瓜的方式来做吧：
#include <iostream>using namespace std;// 时间复杂度为o(n^2), 空间复杂度为o(1), 不符合要求void findSoleNumbers(int a[], int n, int &e1, int &e2){int i = 0;int j = 0;int continueFlag = 0; // 控制外层for, 判断是否过滤当前整数int numberFlag = 0; // 标志第一个、第二个单身整数for(i = 0; i < n; i++){continueFlag = 0;for(j = 0; j < n; j++){if(j != i && a[j] == a[i]){continueFlag = 1;break;}}if(1 == continueFlag) // 该整数是成双成对的， 过滤掉{continue;}// 可怜的单身整数if(0 == numberFlag++){e1 = a[i];}else{e2 = a[i];}}}int main(){{int a[] = {1, 5, 3, 5, 1, 2};int n = sizeof(a) / sizeof(a[0]);int e1 = 0;int e2 = 0;findSoleNumbers(a, n, e1, e2);cout << e1 << endl;cout << e2 << endl;cout << "————————–" << endl;}{int a[] = {1, 1, 2, 5, 4, 5, 2, 4, 3, 0};int n = sizeof(a) / sizeof(a[0]);int e1 = 0;int e2 = 0;findSoleNumbers(a, n, e1, e2);cout << e1 << endl;cout << e2 << endl;cout << "————————–" << endl;}return 0;} 结果为：
32————————–30————————–
上面程序时间复杂度不满足题目要求。当然， 有的朋友可能会想到排序， 思路是可以， 但是， 时间复杂度依然不是o(n), 所以，， 排序法我就不介绍了。
由于数组中整数的范围并没有给出， 所以， 也不太适合用计数的方法来做。 那怎么办呢？ 假如该题目中的整形数组中只有一个单身整数， 那也好办， 如下：
#include <iostream>using namespace std;// 时间复杂度为o(n), 空间复杂度为o(1), 不符合要求void findSoleNumber(int a[], int n, int &e){e = 0;int i = 0;for(i = 0; i < n; i++){e ^= a[i];}}int main(){{int a[] = {1, 5, 3, 5, 1};int n = sizeof(a) / sizeof(a[0]);int e = 0;findSoleNumber(a, n, e);cout << e << endl;cout << "————————–" << endl;}{int a[] = {0, 5, 1, 5, 1, 2, 2};int n = sizeof(a) / sizeof(a[0]);int e = 0;findSoleNumber(a, n, e);cout << e << endl;cout << "————————–" << endl;}return 0;} 结果：
3————————–0————————–
上面的方法尽管没有彻底解决问题， 但已经提供了思路的雏形了， 下面， 我直接给出可行的方法。 代码本身就是最好的解释， 所以不再解释。 代码如下：
#include <iostream>using namespace std;// 在num的二进制中查找第一个出现1的位置int findFirstBitEquOne(int num){int bitIndex = 0;while(bitIndex < 32 && 0 == (num & 1)){num >>= 1;bitIndex++;}return bitIndex;}// 判断num二进制的bitIndex位上的数是否为1bool isBitOne(int num, int bitIndex){return ( (num >>= bitIndex) & 1);}// 时间复杂度为o(n), 空间复杂度为o(1)void findSoleNumbers(int a[], int n, int &e1, int &e2){e1 = 0;e2 = 0;int i = 0;int result = 0;for(i = 0; i < n; i++){result ^= a[i]; // 最后的result肯定是两个单身整数的异或值}int bitIndex = findFirstBitEquOne(result);for(i = 0; i < n; i++){// 对于每一个整数， 根据isBitOne原则进行分组， 两个单身整数必然落在不同的组中， 而成双成对的整数必然落在同一组中if(isBitOne(a[i], bitIndex)) // 组1{//cout << "debug1: " << a[i] << endl;e1 ^= a[i];}else// 组2{//cout << "debug2: " << a[i] << endl;e2 ^= a[i];}}}int main(){{int a[] = {1, 5, 3, 5, 1, 2};int n = sizeof(a) / sizeof(a[0]);int e1 = 0;int e2 = 0;findSoleNumbers(a, n, e1, e2);cout << e1 << endl;cout << e2 << endl;cout << "————————–" << endl;}{int a[] = {1, 1, 2, 5, 4, 5, 2, 4, 3, 0};int n = sizeof(a) / sizeof(a[0]);int e1 = 0;int e2 = 0;findSoleNumbers(a, n, e1, e2);cout << e1 << endl;cout << e2 << endl;cout << "————————–" << endl;}return 0;} 结果如下：
32————————–30————————–
异或的思路， 很巧妙， 以后要注意。好了， 本文先到此为止。
福报不够的人，就会常常听到是非；
