难度中等759
一个整型数组 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
该题是“消失的数字”的进阶版，还没接触的读者可以先看这个：链接：消失的数字
解题思路：
我们依然使用异或的方法，只不过这道题需要查找的是两个数字，所以我们得先找到这两个数字的异或数字：
首先将数组nums中的数字异或一遍，得到的就是只出现一次的数字的那两个数字的异或数字。
又因为该题要求要将returnSize改成只出现一次的数字，这里比较简单，就是两个嘛。
int* singleNumbers(int* nums, int numsSize, int* returnSize){
*returnSize = 2;
int *arr=(int*)malloc(sizeof(int)*2);
int n = 0;
for(int i = 0; i < numsSize; i++)
{
n ^= nums[i];
}
//后续。。。
}现在我们得到了n，那接下来怎么知道n是由哪两个数字组成的呢？
以题目中的例一为例子，现在n的值是7（0111）：
并且我们发现个规律，就是如果n中某一位是1，那肯定是这两个数字之间，其中一个这一位为1，其中一个这一位为0，才能让n的这一位等于1。
所以我们想到一个方法找到这两个数字：
在 n 的二进制位中从右到左，找到第一位为1的位数，然后记下这个位为 j，接着把 nums 中的所有数依次判断，若在 j 位为1则放到一个数组中，为0则放到另一个数组中。最后再对这两个数组分别异或，就能求出这两个数字啦！
以这里例一为例，我们上面求出n等于0111，那么第一位为1的就刚刚好是第一位，然后把nums数组中第一位为1的放到一个数组，为0的放到另一个数组中去。
int j = 0;//用来存放第一个为1的位数
while(n > 0)
{
if(((n>>j) & 1) != 1)
{
j++;
}
else
{
break;
}
}
int arr0[10000] = {0};
int n0 = 0;
int arr1[10000] = {0};
int n1 = 0;
for(int i = 0; i < numsSize; i++)
{
if(((nums[i]>>j) & 1) == 0)
{
arr0[n0] = nums[i];
n0++;
}
else
{
arr1[n1] = nums[i];
n1++;
}
} 最后就是在两个数组中各自求出这两个数字啦，因为这两个数字已经被分离到了两个数组中去了。
int tmp0 = 0;
int tmp1 = 0;
for(int i = 0; i < n0; i++)
{
tmp0 ^= arr0[i];
}
for(int i = 0; i < n1; i++)
{
tmp1 ^= arr1[i];
}
arr[0] = tmp0;
arr[1] = tmp1;
return arr;
int* singleNumbers(int* nums, int numsSize, int* returnSize){
*returnSize = 2;
int *arr=(int*)malloc(sizeof(int)*2);
int n = 0;
for(int i = 0; i < numsSize; i++)
{
n ^= nums[i];
}
int j = 0;//用来存放第一个为1的位数
while(n > 0)
{
if(((n>>j) & 1) != 1)
{
j++;
}
else
{
break;
}
}
int arr0[10000] = {0};
int n0 = 0;
int arr1[10000] = {0};
int n1 = 0;
for(int i = 0; i < numsSize; i++)
{
if(((nums[i]>>j) & 1) == 0)
{
arr0[n0] = nums[i];
n0++;
}
else
{
arr1[n1] = nums[i];
n1++;
}
}
int tmp0 = 0;
int tmp1 = 0;
for(int i = 0; i < n0; i++)
{
tmp0 ^= arr0[i];
}
for(int i = 0; i < n1; i++)
{
tmp1 ^= arr1[i];
}
arr[0] = tmp0;
arr[1] = tmp1;
return arr;
}C++版本：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int tmp = 0;
for(int i = 0; i < nums.size(); ++i)
tmp ^= nums[i];
// tmp就是这两个只出现过一次的数字的异或结果
// 将tmp从低位开始首个出现1的比特位为基准，为tmpi
// 以tmpi处的比特位为0还是1分成两个数组
int tmpi = 0;
while(tmpi < 32)
{
if((tmp >> tmpi) & 1)
break;
tmpi++;
}
vector<int> v1, v2;
for(int i = 0; i < nums.size(); ++i)
{
if((nums[i] >> tmpi) & 1)
v1.push_back(nums[i]);
else
v2.push_back(nums[i]);
}
int a = 0, b = 0;
for(int i = 0; i < v1.size(); ++i)
a ^= v1[i];
for(int i = 0; i < v2.size(); ++i)
b ^= v2[i];
return {a, b};
}
};