找单身狗（数组中数字出现的次数）

一个整型数组 nums 里除两个数字之外&＃xff0c;其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)&＃xff0c;空间复杂度是O(1)。

首先研究一下简化问题&＃xff1a;一个数组中只有一个数字是出现一次&＃xff0c;其他所有数字都出现了两次。

方法一&＃xff1a;

通过排序和两个指针来判断
这个方法时间复杂度和空间复杂度都很高

void bubbleSort(int arr[], int size) {//顺序for (int a &＃61; 0; a < size - 1; a&＃43;&＃43;){//最多size-1轮比较for (int b &＃61; 0; b < size - 1 - a; b&＃43;&＃43;){if (arr[b]>arr[b &＃43; 1]){int c &＃61; arr[b];arr[b] &＃61; arr[b &＃43; 1];arr[b &＃43; 1] &＃61; c;}}}
}int findlone(int* arr1,int size){assert(arr1);bubbleSort(arr1, size);int *one &＃61; arr1;int* two &＃61; arr1 &＃43; 1;while (two){if (*one &＃61;&＃61; *two){one &＃43;&＃61; 2;two &＃43;&＃61; 2;}else{return *one;}}return 0;}


方法二&＃xff08;最优&＃xff09;&＃xff1a;

使用异或

int findlonely(int *arr, int size){int a &＃61; 0;for (int i &＃61; 0; i < size; &＃43;&＃43;i){a &＃61; a^arr[i];}return a;
}


方法三&＃xff1a;

计数法

int find3(int* arr, int size){int num &＃61; 0;for (int i &＃61; 0; i < size; i&＃43;&＃43;){num &＃61; 0;for (int j &＃61; 0; j < size; j&＃43;&＃43;){if (arr[i] &＃61;&＃61; arr[j]){num&＃43;&＃43;;}}if (num &＃61;&＃61; 1){return arr[i];}}return ;
}

完整解法

思路&＃xff1a;
1.将所有元素异或求解&＃xff1b;
2.找出解二进制最低位置的1&＃xff08;只要找个1分开两个数字就可以&＃xff09;&＃xff1b;
3.在位移运算异或求解。

int sumeor(int *arr, int size){int a &＃61; 0;for (int i &＃61; 0; i < size; &＃43;&＃43;i){a &＃61; a^arr[i];}return a;
}
int finddifferentX(int num){int count &＃61; 0;while (count < 32 && (num & 1) &＃61;&＃61; 0){num &＃61; num >> 1;count&＃43;&＃43;;}return count;
}
void findtwosingle(int *arr, int size){if (size < 2){return;}int count &＃61; 0;count &＃61; finddifferentX(sumeor(arr, size));int num1 &＃61; 0;int num2 &＃61; 0;for (int i &＃61; 0; i < size; i&＃43;&＃43;){//arr[i] &＃61; arr[i] >> count;if (((arr[i] >> count)&1) &＃61;&＃61; 0){num1 &＃61; num1^arr[i];}else{num2 &＃61; num2^arr[i];}}printf("%d %d", num1, num2);
}