Given an integer array 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. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0] Output: [-1,0]
Example 3:
Input: nums = [0,1] Output: [1,0]
Constraints:
2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums
will appear twice, only two integers will appear once.This problem requires finding two unique numbers in an array where all other numbers appear twice. The constraints demand a linear time and constant space solution, ruling out simple hash table approaches which would use O(n) space. The optimal solution leverages bit manipulation.
This approach cleverly uses the properties of the XOR operation:
XORing all numbers: The XOR operation is commutative and associative. If we XOR all numbers in the array, numbers that appear twice will cancel each other out (x ^ x = 0). The final result will be the XOR of the two unique numbers (let's call them a
and b
). a ^ b
will be non-zero.
Finding the differentiating bit: We find the least significant bit (LSB) that is set to 1 in a ^ b
. This bit is crucial because it indicates a difference between a
and b
. We use the lowbit
trick (x & -x
) to efficiently find this LSB.
Grouping and XORing again: We iterate through the array again. If a number has the LSB (found in step 2) set to 1, it belongs to one group; otherwise, it's in the other group. By XORing all numbers within each group, we isolate a
and b
.
Time Complexity: O(n) - We iterate through the array twice. Space Complexity: O(1) - We only use a few integer variables.
Code Examples:
The code implementations in various languages follow the algorithm described above. Here are a few examples:
Python:
def singleNumber(nums):
xs = 0
for x in nums:
xs ^= x
lb = xs & -xs
a = 0
for x in nums:
if x & lb:
a ^= x
b = xs ^ a
return [a, b]
Java:
class Solution {
public int[] singleNumber(int[] nums) {
int xs = 0;
for (int x : nums) xs ^= x;
int lb = xs & -xs;
int a = 0;
for (int x : nums) if ((x & lb) != 0) a ^= x;
int b = xs ^ a;
return new int[] {a, b};
}
}
C++:
vector<int> singleNumber(vector<int>& nums) {
int xs = 0;
for (int x : nums) xs ^= x;
int lb = xs & -xs;
int a = 0;
for (int x : nums) if (x & lb) a ^= x;
int b = xs ^ a;
return {a, b};
}
A simpler but less efficient approach (violating the space complexity constraint) would use a hash table (or Set
in Python/Java/JavaScript):
Time Complexity: O(n) Space Complexity: O(n) - The hash table stores up to n/2 elements in the worst case. This is not optimal for the problem's requirements.
This approach is easier to understand but less efficient in terms of space complexity compared to the bit manipulation approach. Therefore, the bit manipulation method is preferred for this LeetCode problem.