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.
Example:
Input: [1,2,1,3,2,5]
Output: [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?
public class Solution {
public int[] singleNumber(int[] nums) {
// Get the XOR of the two numbers we need to find
int diff = 0;
for (int num : nums)
diff ^= num;
// Get its right-most set bit (LSB)
int setBit = diff & (~(diff - 1));
// Now on the basis of this bit, we can divide array into 2 parts
// The one with all the elements with this bit set
// and the other part with this bit unset
// Pass 2 :
int[] ans = { 0, 0 };
for (int num : nums) {
if ((num & setBit) == 0)
ans[0] ^= num;
else
ans[1] ^= num;
}
return ans;
}
}
Last updated