题目
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice.
Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
- The order of the result is not important. So in the above example, [5, 3] is also correct.
- Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
方法
这题是建立在136. Single Number基础上的
假设nums中2个不同的数为a和b，通过计算nums的异或运算就能求出a和b的异或值，定为c。那么c的二进制表示中，从右开始数的第一个1即为a和b的二进制形式在该位上肯定是不同的值。
假如a = 0101, b = 0011, 那么a^b=0110, 那么a和b是在从右往左数的第二位值不同。设置bit=010，将nums里的每个数&bit, 便可将nums分成2组了，每组的异或值就是a或者b了。
c代码
#include <assert.h>
#include <stdlib.h>
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumber(int* nums, int numsSize, int* returnSize) {
int i = 0;
int result = 0;
for(i = 0; i < numsSize; i++) {
result ^= nums[i];
}
// int bit = result & (~(result-1));
int bit = 1;
while((result & 1) == 0) {
bit <<= 1;
result >>= 1;
}
int result1 = 0;
int result2 = 0;
for(i = 0; i < numsSize; i++) {
if((nums[i] & bit) == 0)
result1 ^= nums[i];
else
result2 ^= nums[i];
}
int* singleNums = (int *)malloc(sizeof(int)*2);
singleNums[0] = result1;
singleNums[1] = result2;
*returnSize = 2;
return singleNums;
}
int main() {
int returnSize = 0;
int nums[6] = {1,1,2,2,3,5};
int* singleNums = singleNumber(nums, 6, &returnSize);
assert(returnSize == 2);
assert(singleNums[0] == 5);
assert(singleNums[1] == 3);
return 0;
}
