LeetCode 题解工作台
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 示例 1 ： 输入： nums = [2,2,1] 输出： 1 示例 2 ： 输入： nums = …
2
题型
10
代码语言
3
相关题
当前训练重点
简单 · 数组·结合·位运算·操作
答案摘要
异或运算的性质： - 任何数和 做异或运算，结果仍然是原来的数，即 $x \oplus 0 = x$；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·位运算·操作 题型思路
题目描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
解题思路
方法一：位运算
异或运算的性质：
- 任何数和 做异或运算，结果仍然是原来的数，即 ；
- 任何数和其自身做异或运算，结果是 ，即 ；
我们对该数组所有元素进行异或运算，结果就是那个只出现一次的数字。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(xor, nums)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate shows an understanding of bitwise operations, especially XOR, and how it can be used to efficiently solve problems with unique constraints.
- question_mark
The candidate provides an optimal solution that minimizes both time complexity and space usage, which is crucial for scalability in large datasets.
- question_mark
The candidate demonstrates the ability to understand and apply problem-specific constraints, such as the need for constant space and linear runtime.
常见陷阱
外企场景- error
A common mistake is to use extra space for storing values or counting occurrences (e.g., using a hash map or sorting), which violates the constant space constraint.
- error
Failing to recognize that XOR is the most efficient way to solve this problem can lead to slower, suboptimal solutions that use extra time and space.
- error
Not understanding the properties of XOR can lead to incorrect logic, such as assuming that XOR only works on pairs of identical numbers instead of all duplicates.
进阶变体
外企场景- arrow_right_alt
Handling arrays with negative numbers, ensuring the XOR approach works regardless of sign.
- arrow_right_alt
Solving the problem with an alternative bit manipulation technique, such as using bitwise AND/OR to achieve similar results.
- arrow_right_alt
Working with arrays of varying sizes, from small arrays to large datasets, while maintaining linear time and constant space.