程序员面试金典 - 面试题 17.04. 消失的数字

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

• 数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O(n)时间内完成吗？

• 注意：本题相对书上原题稍作改动

示例 1：

• 输入：[3,0,1]
• 输出：2

示例 2：

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

题目思考

1. 如何在 O(n) 时间内完成?

解决方案

思路

• 根据题目描述, 在范围 0 ～ n 内的 n + 1 个数字中只缺失了其中一个
• 所以我们可以求 1~n 的和, 然后减去数组本身所有数字的和, 这样得到的数字就是缺失的

复杂度

• 时间复杂度 O(N): 需要求数组元素的和
• 空间复杂度 O(1): 只需要维护常数个变量

代码

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # 利用前n项和求和公式, 减去数组本身所有数字的和
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊