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?

Answer:

Take a look at my previous post: http://maxinrui.com/index.php/2016/09/27/136-single-number-leetcode/

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

Assume there are b and c that only appear once in the array, so, if we follow the same steps, perform XOR operation on each array elements, we could end up getting b ^ c;

What could b ^ c do for us?

It would be much simpler if the array can be split into two arrays that each only contain b or c, then we just do a XOR to all elements in each array, we could get the b and c.

That’s what b ^ c can do for us.

As we know, there must be a Kth bit of b and c that is different, otherwise they will be the same. Find the Kth bit that is different, we can use that to split the array into two arrays.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public class Solution { private int getXOR(int[] nums) { int result = 0; for (int i = 0; i < nums.length; i++) { result ^= nums[i]; } return result; } public int[] singleNumber(int[] nums) { int[] results = new int[2]; int xorNumber = getXOR(nums); int k = 0; while ((xorNumber & 1) == 0) { xorNumber = (xorNumber >>> 1); k++; } int[] nums1 = new int[nums.length]; int[] nums2 = new int[nums.length]; for (int i = 0; i < nums.length; i++) { if (((nums[i] >>> k) & 1) != 1) { nums1[i] = nums[i]; } else { nums2[i] = nums[i]; } } int result1 = getXOR(nums1); int result2 = getXOR(nums2); results[0] = result1; results[1] = result2; return results; } } |

## Recent Comments