剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数

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

示例 1：

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

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
 

限制：

2 <= nums.length <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

首先了解下位运算的基础

&
按位与
如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

|
按位或
两个相应的二进制位中只要有一个为1，该位的结果值为1

^
按位异或
若参加运算的两个二进制位值相同则为0，否则为1

~
取反
~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1

<<
左移
用来将一个数的各二进制位全部左移N位，右补0

>>
右移
将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

思路：

1. 设一个ret=0,将数组中所有的数和ret异或一下，假设出现一次的两个数是x 与 y ,ret就是x^y

2. 找ret里面随便一个为1的位（二进制形式）
ret的第n位为1，说明x与y的第n为一个为1一个为0。
将原数组中的数，第n位为1的分为一组，第n位为0的分为一组

eg：对 1 3 1 2 5 2这段数组。

思路转化成代码的难点，就是找到ret中为1的位我们可以用&与<< 来进行判断

ret是int类型的一共有32个比特位。按位与的特点是：如果两个相应的二进制位都为1，则该位的结果值为1，否则为0。我们根据按位与并结合1进行判断。

方法如下：

ret&(1<

同理也可以用 1&(ret>>j)  进行判断，两者的效果是等价的。

eg：对ret=12这个数进行判断它的二进制第几位是1

图解：

  

    这里说一下returnSize的作用，它是一个输出型参数，力扣这样设计是为了知道返回的数组中有几个值，并且它传的形参是int * 类型的，原因是形参的改变不回影响实参的改变所以就得传地址.

代码：

int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
    int ret=0;
    for(int i=0;i>j & 1)
        break;
    }

    //通过第j位为1,0 进行分组,分为2组，第j位为1的分为A组，第j位为0的分为b组
    //x与y 一定会分别进入两组
    //最终对两组分别进行异或就得到x与y  
    int x=0,y=0;
    for(int k=0;k>j & 1) //位运算的优先级低，加括号
        {
            x^=nums[k];
        }
        else
        {
            y^=nums[k];
        }

    }

    int *arr=(int *)malloc(sizeof(int)*2);
    arr[0]=x;
    arr[1]=y;
    *returnSize=2; //表明返回值是2个

    return arr;

}

 这个地方不建议写成  if(ret&(1<

解决方法：1.用另一种等价的方法 2 。用long 类型的1

ps:之前的力扣，if(ret&(1<