题目难度: 中等
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。
- 2 <= nums.length <= 10000
题目样例
示例
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
题目思考
- 如果其他数字都出现两次, 只有一个数字出现一次如何解决?
- 如何做到空间复杂度是 O(1)?
解决方案
思路
- 分析题目, 相信大家都能想到计数字典的方案, 就是记录每个数字的次数, 然后找次数为 1 的数字, 但这样空间复杂度为 O(N), 不满足要求
- 我们先来分析一个简化问题: 如果其他数字都出现两次, 只有一个数字出现一次如何解决?
- 这个问题估计不少同学都见过, 一个很巧妙的做法是异或所有数字, 因为两个相同数字的异或结果一定为 0, 所以最终异或的结果一定是那个出现一次的数字
- 那针对这道题, 还可以利用异或思路吗?
- 答案是肯定的, 假设我们还是异或所有数字, 那么最终异或出来的值等价于那两个出现一次的数字的异或结果, 因为其他出现两次的数字异或都是 0, 对最终异或结果没有影响.
- 而异或结果中的某一位 1, 代表这两个数字在这一位上的取值不同, 一个是 0, 一个是 1
- 我们可以利用这一点, 将原数组分为两类, 一类是该位为 1 的, 一类是该位为 0 的. 对于出现两次的数字而言, 它们肯定落在同一类里面; 而对于这两个出现一次的数字, 它们被分属在两个不同类中.
- 这样问题就转换成了上面描述的简化问题, 只需要对这两类分别求出它们的异或结果, 自然就是对应两个出现一次的数字了~
- 最后一个问题: 如何求异或结果 xor 的某一位 1 呢?
- 我们可以利用循环, mask 从 1 开始, 判断 xor 的这一位是否为 1, 是的话就跳出循环, 否则 mask 左移一位, 直到超出 xor
- 当然还有更简单的做法, 利用树状数组的 lowbit, 也即
xor & -xor, 直接就能求得最低位的 1 对应的数字, 这个大家手动模拟下补码就知道是为什么了
- 下面代码对必要的步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度 O(N): 遍历两遍数组
- 空间复杂度 O(1): 只使用了几个变量
代码
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
# 先拿到所有数字的异或结果, 该结果一定至少有一位是1, 否则就不可能有两个出现一次的数字
xor = 0
for n in nums:
xor ^= n
# 然后随便针对异或结果的某一位1, 将原数组分为两类, 自然两个出现一次的数字就会分别落在不同类里面, 否则其异或结果的这一位不可能是1
# 这里直接利用树状数组的lowbit(即原来的数字的最低位的1)
mask = xor & -xor
a, b = 0, 0
for n in nums:
if n & mask:
# 如果数字的这一位是1, 归为一类, 求它们的异或值, 即为其中一个出现一次的数
a ^= n
else:
# 如果数字的这一位是0, 归为另一类, 求它们的异或值, 即为另一个出现一次的数
b ^= n
return [a, b] 大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
京公网安备 11010502036488号