给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。python
时间: 2024-01-30 22:09:38 浏览: 30
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。要找出只出现一次的那两个元素,可以使用异或运算。首先将所有元素进行异或运算,得到的结果是两个只出现一次的元素的异或结果。然后根据异或结果的二进制表示中的任意一位,将原数组中的元素分成两组,分别对这两组元素进行异或运算,得到的结果就是两个只出现一次的元素。
以下是Python代码实现:
```python
def findSingleNums(nums):
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]
```
其中,`xor`表示所有元素的异或结果,`mask`表示异或结果的二进制表示中的某一位,`a`和`b`分别表示两个只出现一次的元素。在第一个循环中,计算出`xor`的值;在第二个循环中,根据`mask`的值将原数组中的元素分成两组,并对这两组元素进行异或运算,得到`a`和`b`的值。
相关问题
给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。要找出只出现一次的那两个元素,可以使用异或运算。首先将所有元素进行异或运算,得到的结果是两个只出现一次的元素的异或结果。然后根据异或结果的二进制表示中的任意一位,将原数组中的元素分成两组,分别对这两组元素进行异或运算,得到的结果就是两个只出现一次的元素。
具体步骤如下:
1. 对整个数组进行异或运算,得到两个只出现一次的元素的异或结果。
2. 找到异或结果中任意一位为1的位置,记为k。
3. 根据第k位是否为1,将原数组中的元素分成两组,分别对这两组元素进行异或运算,得到的结果就是两个只出现一次的元素。
代码如下(Python):
```python
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for num in nums:
xor ^= num
k = 0
while xor & (1 << k) == 0:
k += 1
a, b = 0, 0
for num in nums:
if num & (1 << k):
a ^= num
else:
b ^= num
return [a, b]
```
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素
这道题可以使用异或运算来解决,具体步骤如下:
1. 首先对整个数组进行一次异或运算,得到的结果就是两个只出现一次的元素的异或结果。
2. 因为这两个元素不相同,所以它们的二进制表示中至少有一位是不同的。我们可以根据这一位将所有元素分成两组,一组该位是 0,一组该位是 1。然后分别对这两组进行异或运算,得到的结果就是两个只出现一次的元素。
下面是代码实现:
```python
def findSingleNums(nums):
# 对整个数组进行异或运算
xor = 0
for num in nums:
xor ^= num
# 找到两个只出现一次的元素在二进制下不同的那一位
mask = 1
while (mask & xor) == 0:
mask <<= 1
# 根据这一位将所有元素分成两组
a, b = 0, 0
for num in nums:
if num & mask:
a ^= num
else:
b ^= num
return a, b
```
时间复杂度为 O(n),空间复杂度为 O(1)。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)