直销网站建设 优帮云seo广告投放

问题详情

剑指 Offer 56：

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

示例：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

分析问题

首先我们知道两个相同的数异或结果是0，而0异或任何数都是不变的；，而且异或运算是支持交换律和结合律；

C语言中的异或符号是’^’

如：3⁵3=3³5=0^5=5;

那如果数组nums中只有一个数出现一次，其它的数都出现了两次，那我们将所有的数组元素进行异或运算，不就可以得出结果了吗？

但是，在这里有两个只出现一次的数字，我们该怎么办呢，如果我们也将其所有的数组元素都异或在一起，那得出的数是不是就是那两个出现一次的数字异或的结果：

例：[1,1,2,3,4,4,5,5]

2 = 0010;3 = 0011

所以1¹2³4⁴5^5 = 0²3 = 0001 = 1

那我们能不能将这两个数分开来呢？使这两个单独出现的数在它们所在的数组都是单独存在的。再分别异或，就能得出这两个数。

那如何分出这两个数呢：

我们先把数组nums中所有元素异或起来。

1¹2³4⁴5^5 = 0²3 = 0011^0010 = 0001

相同的数异或为0，0与非0数异或为非0数本身。 所以，全部异或在一起就等价于两个单独数异或.

异或得出值0001，设这个值为ret 。通过观察可以发现，ret为1的位，就说明两个单独数的相同位是不同的。要么是1要么是0。不可能重复。

那我们如何去找到为1的位：

我们定义一个变量m = 1；将1（00000000000000000000000000000001）不断地左移m位，与ret进行&运算，如果结果为非0，那此时，1对应的位就是1向左移m位对应1的位置：

回到刚刚的数组：通过这个为1的位，和原数组中所有元素进行&运算，就可以把两个单独出现的数分开。其他出现两次的数因为二进制值相同也会共同出现在同一边。

到这我们写出这个程序就不难了。

代码展示

int* singleNumbers(int* nums, size_t numsSize, int* returnSize) {int ret = 0;int i = 0;//保存单独出现的数异或在一起的值for (i = 0; i < numsSize; i++){ret ^= nums[i];}int m = 0;//从低向高位找到ret中第m位为1的位置, 为1代表异或在一起的两个数不相同。//while (m < 32){if (ret & (1 << m)){break;}else{m++;}}int x = 0;//记录单独出现的数int y = 0;//记录单独出现的数for (i = 0; i < numsSize; i++){if (nums[i] & (1 << m)) //&为1的为一组 直接全部异或到一起记录其值{x ^= nums[i];}else  //为0的为一组{y ^= nums[i];}}int* retArr = malloc(2 * sizeof(int));retArr[0] = x;retArr[1] = y;*returnSize = 2;return retArr;
}int main()
{int p = 0;int arr[] = { 1,2,55,55,66,66 };int* a = singleNumbers(arr, sizeof(arr) / sizeof(int), &p);printf("%d ", a[0]);printf("%d ", a[1]);free(a);a = NULL;printf("%d ", p);return 0;
}