LeetCode 题解工作台
只出现一次的数字 III
给你一个整数数组 nums ，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1： 输入： nums = [1,2,1,3,2,5] 输出： [3,5] …
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·位运算·操作
答案摘要
异或运算有以下性质： - 任何数和 做异或运算，结果仍然是原来的数，即 $x \oplus 0 = x$；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·位运算·操作 题型思路
题目描述
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1：
输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0] 输出：[-1,0]
示例 3：
输入：nums = [0,1] 输出：[1,0]
提示：
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- 除两个只出现一次的整数外，
nums中的其他数字都出现两次
解题思路
方法一：位运算
异或运算有以下性质：
- 任何数和 做异或运算，结果仍然是原来的数，即 ；
- 任何数和其自身做异或运算，结果是 ，即 ；
由于数组中除了两个数字之外，其他数字都出现了两次，因此我们对数组中的所有数字进行异或运算，得到的结果即为两个只出现一次的数字的异或结果。
而由于这两个数字不相等，因此异或结果中至少存在一位为 。我们可以通过 lowbit 运算找到异或结果中最低位的 ，并将数组中的所有数字按照该位是否为 分为两组，这样两个只出现一次的数字就被分到了不同的组中。
对两个组分别进行异或运算，即可得到两个只出现一次的数字 和 。
时间复杂度 ，其中 为数组长度。空间复杂度 。
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xs = reduce(xor, nums)
a = 0
lb = xs & -xs
for x in nums:
if x & lb:
a ^= x
b = xs ^ a
return [a, b]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because every number is XORed twice, once for the total xorResult and once in partitioning. Space complexity is O(1) as only a few variables are needed for XOR calculations. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect a linear time and constant space solution using bitwise operations.
- question_mark
They may hint at XOR or ask how to distinguish two unique numbers.
- question_mark
Watch for questions about edge cases like negative numbers or minimal array length.
常见陷阱
外企场景- error
Attempting to use a hash map violates constant space requirement.
- error
Not correctly identifying the distinguishing bit can mix up the two unique numbers.
- error
Forgetting that XOR of duplicates cancels out may lead to incorrect grouping.
进阶变体
外企场景- arrow_right_alt
Single Number I: Only one unique number appears, all others twice.
- arrow_right_alt
Single Number II: Every number appears three times except one unique number.
- arrow_right_alt
Find k unique numbers using generalized bit manipulation and partitioning.