Single Number III

描述

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:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

分析

x, y是那两个未知数，那么如果对这个数组做异或的话，结果实质上等于x ^ y，因为其他数都出现了两次，被抵消了。

代码

// Single Number III
// Time Complexity: O(log n), Space Complexity: O(1)
public class Solution {
public int[] singleNumber(int[] nums) {
int xorResult = 0;
for (int x : nums) {
xorResult ^= x;
}

// get the index of first 1
int k = 0;
for (k = 0; k < Integer.SIZE; ++ k) {
if (((xorResult >>> k) & 1) == 1) {
break;
}
}

// use k to split the array into two subarrays
// XOR result of the first subarray
int xorResult2 = 0;
for (int x : nums) {
if (((x >>> k) & 1) == 1) {
xorResult2 ^= x;
}
}
return new int[] {xorResult2, xorResult ^ xorResult2};
}
}