题目
一个整型数组 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]
解法1：用异或取出能够区分两单数的bit，然后再各自异或取得
int* singleNumbers(int* nums, int numsSize, int* returnSize){
if (nums == NULL || numsSize < 2) {
if (returnSize) *returnSize = 0;
return NULL;
}
*returnSize = 2;
int *res = (int *)calloc(2, sizeof(int));
int exo = 0;
for(int i = 0; i < numsSize; i++)
exo ^= nums[i]; //两个单数的异或
int diffBit = 1;
while(!(exo & diffBit))
diffBit <<= 1; //取做以区分的bit
for(int i = 0; i < numsSize; i++)
if (nums[i] & diffBit)
res[0] ^= nums[i]; //其中某个单数的异或
else
res[1] ^= nums[i];
return res;
}
解法2：用异或取出能够区分两单数的bit，异或取出其中一个即可
int* singleNumbers(int* nums, int numsSize, int* returnSize){
if (nums == NULL || numsSize < 2) {
if (returnSize) *returnSize = 0;
return NULL;
}
*returnSize = 2;
int *res = (int *)calloc(2, sizeof(int));
for(int i = 0; i < numsSize; i++)
res[0] ^= nums[i]; //两个单数的异或
int diffBit = 1;
while(!(res[0] & diffBit))
diffBit <<= 1;
for(int i = 0; i < numsSize; i++)
if (nums[i] & diffBit)
res[1] ^= nums[i]; //其中某个单数的异或
res[0] ^= res[1]; //利用已有的异或结果
return res;
}
| 
转播
