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 }
