给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
时间: 2024-01-30 17:09:38 浏览: 79
找出只出现一次的数字
5星 · 资源好评率100%
题目描述:给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
解题思路:使用异或运算,将所有元素异或起来,得到的结果就是两个只出现一次的元素异或的结果。因为这两个元素不相同,所以异或结果中至少有一位是1,找到这个1所在的位置,然后将数组中所有元素按照这个位置是否为1分成两组,这样两个只出现一次的元素就被分到了不同的组中,然后对每组中的元素分别异或,得到的结果就是这两个只出现一次的元素。
参考代码:
```python
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for num in nums:
xor ^= num
mask = 1
while xor & mask == 0:
mask <<= 1
a, b = 0, 0
for num in nums:
if num & mask == 0:
a ^= num
else:
b ^= num
return [a, b]
```
阅读全文