[好题!] 剑指offer 56 找出现一次的两个数字

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

leetcode中一共有4个这样的题, 特点都是: 其他的数字出现次数相同, 这(几)个数字出现的次数和他们不同. 解决方法都是通过异或, 把这几个数的特征提取出来.

这道题还有拓展: 提取出来的也是两个数的特征和, 如何分离?

根据xor结果的某一位, 如果是1的话, 证明在这一位上, 这两个数是不同的.

将原来的数组分成两组, 一组在这一位是0, 一组在这一位是1. 那么这两个组的分别的异或结果就是这两个数.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize){
    *returnSize = 0;
    if(!nums) return NULL;
    *returnSize = 2;
    if(numsSize == 2 ) return nums;

    //计算所有数字的xor
    int xor = 0, i = 0;
    while(i < numsSize)
    {
        xor ^=nums[i];
        i++;
    }

    //计算从最低位起第一个非0位,位置为bit
    int tempxor = xor, bit = 0;
    while(tempxor%2 == 0)
    {
        bit++;
        tempxor /= 2;
    }

    //分为2组, bit位为0的一组, bit位为1的为一组
    //两个数一定在 不同的分组里
    int xor1= 0, xor2 = 0, j;
    i = 0;
    while(i < numsSize)
    {
        int temp = nums[i];
        j  = bit;
        while(j > 0)
        {
            j--;
            temp /= 2;
        } 
        if(temp % 2 == 0)
            xor1 ^= nums[i];
        else
            xor2 ^= nums[i];
        i++;
    }
    
    int *result = malloc(sizeof(int) * 2);
    result[0] = xor1;
    result[1] = xor2;

    return result;

}