Sui Xin's Blog

[LeetCode]268. 缺失数字（Missing Number）

Posted on In Disqus:

题目描述

给定一个包含 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

Related Posts