NC101 缺失数字

发表于 更新于 分类于 ， ， Waline： 本文字数： 261 阅读时长 ≈ 1 分钟

NC101 缺失数字

知识点

位运算
数组
数学
二分

描述

从 0,1,2,…,n 这 n+1 个数中选择 n 个数，选择出的数字依然保持有序，找出这 n 个数中缺失的那个数，要求$O(n)$或 $O(log(n))$ 并尽可能小。

数据范围： $0\leq n \leq 10000$
要求： 空间复杂度 $O(1)$ ，时间复杂度 $O(n)$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入：

1
[0,1,2,3,4,5,7]

返回值：

1
6

示例2

输入：

1
[0,2,3]

返回值：

1
1

示例3

输入：

1
[0,1,2,3,4]

返回值：

1
5

关联企业:

字节跳动
华为
百度