LeetCode 题解工作台
丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。 示例 1： 输入： nums = [3,0,1] 输出： 2 解释： n = 3 ，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 n…
6
题型
8
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
异或运算的性质： - 任何数和 做异或运算，结果仍然是原来的数，即 $x \oplus 0 = x$；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
解题思路
方法一：位运算
异或运算的性质：
- 任何数和 做异或运算，结果仍然是原来的数，即 ；
- 任何数和其自身做异或运算，结果是 ，即 ；
因此，我们可以遍历数组，将数字 与数组中的元素进行异或运算，最后的结果就是缺失的数字。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return reduce(xor, (i ^ v for i, v in enumerate(nums, 1)))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate’s ability to use a mathematical formula or XOR manipulation for efficiency.
- question_mark
Observe the clarity in how the candidate justifies the choice of approach for handling time and space constraints.
- question_mark
Check for an understanding of array scanning and hash table concepts, especially for large inputs.
常见陷阱
外企场景- error
Mistaking the problem for a simple search rather than recognizing the need for a missing number in the full range.
- error
Choosing an approach with excessive space complexity when an O(1) space solution is possible.
- error
Failing to handle edge cases like when n is 1, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Allow duplicates in the array, or change the range from [0, n] to [1, n].
- arrow_right_alt
Handle a missing number in an array containing negative numbers in the range.
- arrow_right_alt
Modify the input array to become unsorted, forcing the candidate to consider sorting or hash-based solutions.