找出数组中两个只出现一次的数（c语言实现）

找出数组中两个只出现一次的数（c语言实现）

一、问题描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

二、思路

先取所有数字异或。假如结果的二进制为10100，因为第三位为1，我们可以得知目标数的第三位不同，然后用二进制数00100和每一个数按位与，这样就把所有的数分为两部分，且目标数不在一起，相同的数在一起。再把每一部分的数异或就可以得到结果。

三、具体代码

int* singleNumbers(int* nums, int numsSize) {
	//创建一个数组，用来接收得到的结果并作为返回值
	int* arr = (int*)malloc(sizeof(int) * 2);
	arr[0] = arr[1] = 0;
	//先取所有数字异或，得到两个目标数的异或
	int ret = 0;
	for (int i = 0; i < numsSize; i++) {
		ret ^= nums[i];
	}
	//得到标志数，用来后面的分组
	int flag = 1;
	while ((ret & flag) == 0) {
		flag = flag << 1;
	}
	for (int i = 0; i < numsSize; i++) {
		if (nums[i] & flag) {
			arr[0] ^= nums[i];
		}
		else {
			arr[1] ^= nums[i];
		}
		
	}
	return arr;
}
int main() {
	int nums1[4] = { 1,1,2,4 };
	int size = sizeof(nums1) / sizeof(nums1[0]);
	int nums2[2] = { 0 };
	int* p = nums2;
	p = singleNumbers(nums1, size);
	for (int i = 0; i < 2; i++) {
		printf("%d ", p[i]);
	}
	system("pause");
}