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.
时间: 2024-03-02 10:52:32 浏览: 57
# 在一个数组中除了一个数字只出现1次外,其他均出现2次,求这个数字
To solve this problem, we can use the XOR operation.
First, we XOR all the elements in the array. The result of this XOR operation will be the XOR of the two elements that appear only once.
Since the two elements are distinct, their XOR result must have at least one bit that is 1. We can use this bit to partition all the elements in the array into two groups: one group that has this bit set to 1, and another group that has this bit set to 0.
The two elements we are looking for must be in different groups, because if they were in the same group, their XOR result would cancel out the bit that we used to partition the groups.
Finally, we XOR all the elements in each group separately. The results will be the two elements we are looking for.
Here's the Python code to implement this algorithm:
```python
def singleNumber(nums):
# XOR all elements
xor_result = 0
for num in nums:
xor_result ^= num
# Find the rightmost bit that is 1
rightmost_bit = 1
while rightmost_bit & xor_result == 0:
rightmost_bit <<= 1
# Partition the elements into two groups
group1 = []
group2 = []
for num in nums:
if num & rightmost_bit:
group1.append(num)
else:
group2.append(num)
# XOR all elements in each group separately
result1 = 0
for num in group1:
result1 ^= num
result2 = 0
for num in group2:
result2 ^= num
return [result1, result2]
```
Note that this algorithm has a time complexity of O(n) and a space complexity of O(1).
阅读全文