数组nums包含从0到n的所有整数 但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗
示例
输入 [3,0,1]
分析 直观上的一种解法是对数组中的所有数字相加 然后与1到n的和求差值 差值就是缺失的整数。第二种解法充分利用到异或运算特性 即异或运算具备交换律和结合律 a^b ^a b, a ^a 0, a ^0 a, 对数组中所有的数字进行异或运算 然后与1到n的数进行异或运算 最终的结果就是缺失的值。
方法1 求和取差值
class Solution: def missingNumber(self, nums: List[int]) - int: n len(nums) for i in range(1, n 1): S - nums[i-1] return S
方法2 异或运算
class Solution: def missingNumber(self, nums: List[int]) - int: miss_num 0 n len(nums) for i in range(1, n 1): miss_num ^ i miss_num ^ nums[i-1] return miss_num
