leetcode：只出现一次的数字Ⅲ（详解）

题目：

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路：

1 所有数字异或，结果是只出现一次的两个数字的异或结果

  （异或：相同为0，相异为1，0与任何数异或都是数字本身）

2 得到答案的两个数字异或的结果，区分这两个数字：

    （这两个数字互不相同，则一定在某些二进制位上，一个数字是1，另一个数字则对应是0）

异或的结果，它所有的二进制位中一定存在二进制位为1的，此位置的二进制位就可以区分

a 在异或结果中找到一个可以区分两个数字的二进制位

   数字&(-数字）：可以得到此数字二进制位中最低位的1，这里称之为j

   那么异或结果&(-异或结果）：就是异或结果二进制位中最低位的1

注意：若异或结果是INT_MIN，即（-2147483648）

           原码： 1000 0000  0000  0000  0000  0000  0000  0000

          用于位运算的补码溢出了

          所以当异或结果为INT_MIN时，异或结果本身就是最低位的1，不用进行位运算

INT_MAX :0111 1111 1111 1111 1111 1111 1111 1111

-INT_MAX的补码：1000 0000 0000 0000 0000 0000 0000 0001

都没有溢出，所以INT_MAX是可以进行位运算来获取INT_MAX二进制中最低位的1

如：3： 00000000 00000000 00000000 00000011（整数的原码，反码，补码都相同）

       -3的原码： 10000000 00000000 00000000 00000011（位运算都要用补码）

     -3的反码：    11111111 11111111 11111111 11111100（原码的符号位不变，其他位按位取反）

    -3的补码：     11111111 11111111 11111111 11111101（补码+1）

3&（-3）：00000000 00000000 00000000 00000011

              &   11111111 11111111 11111111 11111101

结果：        00000000 00000000 00000000 00000001（3最低位的那个1）

再如：

 

b 根据j，将所有数字划分成两个阵营，分别异或在一起

    出现两次的数字一定在同一阵营，异或一定为0

    某数字&j为1：表示此数字在作为区分的二进制位上数值为1

    某数字&j为0：表示此数字在作为区分的二进制位上数值为0

    最终两阵营的结果就是两个答案了

代码实现：

class Solution
{
public:vector<int> singleNumber(vector<int>& nums){int k = 0;//所有数字异或的结果for(auto e:nums){k^=e;}int j =k==INT_MIN?k: k&(-k);//异或结果二进制中最低位的1int ret1 = 0;int ret2 = 0;for(auto e:nums){if(e&j)//在作为区分的二进制上数值为1{ret1^=e;}else在作为区分的二进制上数值为0{ret2^=e;}}return {ret1,ret2};}
};