文章目录
- 题目描述
- 思路分析
- 完整代码
题目描述
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
思路分析
题目要求了时间和空间复杂度,就不能暴力和哈希表了。
之前有做个一个题,是在数组中找到仅仅出现了一次的数。那个题的思路是用异或。即 A和A异或 结果为0。 ABABC 五个数异或,则结果为C。
给忘了的同学提醒一下:
- 异或:相同为0,不同为1.
- 与:双1则1,否则0.
本题是 一个数组里有两个只出现了一次的数,那么是否可以将整个数组分组,让两个只出现了一次的数分别在两个分组里?
分组步骤:
- 首先设两个只出现了一次的数为X和Y。算出X和Y的异或值,记为xor。
- 由于X不等于Y,所以xor中必有一位是1。设一个变量mask = 1,让mask和xor进行
与
操作,若与
操作结果为0,则让mask右移一位。该操作目的是找到xor右数第一位为1的位数。比如xor= 110 。 则mask结果会为010。即右数第二位是第一个出现的1。 - 用mask来对原数组进行分组,mask与原数组值进行
与
操作,为0的分为一组,为1的分为一组。由于X不等于Y,所以两者必有一位不同,必能分到两个组里,而原数组中相同的数,他们和一个mask进行与
操作,必然能分到一个组里。 - 最后对两个组分别进行异或操作,就能得到两个不同的数了。
完整代码
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
# 异或找到X和Y的异或值
xor = 0
for i in nums:
xor ^=i
# 找到该异或值的从右数的第一个1
mask = 1
while xor & mask == 0:
mask<<=1
# 用该分割值分割两个数组,分别进行遍历找到X和Y
x = 0
y = 0
for i in nums:
if i&mask==0:
x^=i
else:
y^=i
return x,y