一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

这里写目录标题

• 问题详情
• 分析问题
• 代码展示

问题详情

剑指 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;
}