最后更新于4年前
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
示例 2:
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
由于题目限定了只缺失了一个数, 因此求0, 1, 2, ..., n的总和, 减去数组所有数字之和, 差值就是缺失的数字.
由于异或运算满足结合律, 并且对一个数进行两次完全相同的异或运算会得到原来的数, 因此我们可以通过异或运算找到缺失的数字.
我们将0, 1, 2, ..., n这个数字进行异或, 然后在对数组中的每个数字进行异或, 在数组中出现过的数字, 都可以找到相同的数字进行异或, 化为0, 在数组中没有出现过的数字, 就会被留下.
输入: [3,0,1] 输出: 2
输入: [9,6,4,2,3,5,7,0,1] 输出: 8
class Solution: def missingNumber(self, nums: List[int]) -> int: n = len(nums) missing = 0 for i in range(n): missing ^= i ^ nums[i] missing ^= n return missing