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?
1 /**
2 * Return an array of size *returnSize.
3 * Note: The returned array must be malloced, assume caller calls free().
4 */
5 int* singleNumber(int* nums, int numsSize, int* returnSize) {
6 int flag = 0;
7 int i;
8 int k = 1;
9 int *res;
10 res = (int*)malloc(2 * sizeof(int)); //必须malloc 不然通不过
11 res[0] = res[1] = 0;
12 for(i = 0; i < numsSize; i++) //先异或出这2个数
13 flag ^= nums[i];
14 while(1)
15 {
16 if(k & flag) // 找出二进制中第一个为1的位，那么这2个数这个位，其中一个为1，另外一个为0
17 break;
18 k = k << 1;
19 }
20 for(i = 0; i < numsSize; i++)
21 {
22 if(k & nums[i]) //把所有这位为1的归位一类，
23 res[0] ^= nums[i]; //异或出这位为0的数
24 else //同理异或处这位位1的数
25 res[1] ^= nums[i];
26
27 }
28 *returnSize = 2;
29 return res;
30 }