[LeetCode]268. 缺失数字(Missing Number)

题目描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解题思路

  1. 解法一:排序+check。时间复杂度为 O(n log n)
  2. 解法二:哈希表。空间复杂度为 O(n)
  3. 解法三:异或运算。将序列中的所有数字做异或运算,再对 0 到 n 的所有数字做异或运算,最后的结果即为没有出现过的数字。
  4. 解法四:求和公式。将 0 到 n 的和算出来,再依次减去序列中的每个数组。

代码

Python 3.6

解法三:异或运算

1
2
3
4
5
6
7
8
class Solution:
def missingNumber(self, nums: List[int]) -> int:
missing = 0
for i, num in enumerate(nums):
missing ^= i
missing ^= num
return missing ^ len(nums)

执行用时:304 ms
内存消耗:15.2 MB

解法四:求和公式

1
2
3
4
5
6
7
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
sum_nums = int(n * (n + 1) / 2)
for num in nums:
sum_nums -= num
return sum_nums

执行用时 : 280 ms
内存消耗 : 15.1 MB

参考

https://leetcode-cn.com/problems/missing-number/solution/que-shi-shu-zi-by-leetcode