一、题目描述
从 0,1,2,…,n 这 n+1 个数中选择 n 个数，选择出的数字依然保持有序，找出这 n 个数中缺失的那个数，要求 O(n) 或
O(log(n)) 并尽可能小。
示例:
输入：[0,1,2,3,4,5,7]
返回值：6
输入：[0,2,3]
返回值：1
二、解题思路:
(一) 二分查找
class Solution:
def solve(self , a ):
# write code here
# n = len(a) - 1
# if n == 0: return 0
# if a[0] != 0: return 0
# if a[-1] + 1 == n: return n
### 初始化双指针
left, right = 0, len(a) - 1
while left <= right:
# 确定二分中点
m = (left + right) // 2
# 如果 a[m] == m，则未知的数字在 【m+1, j】
if a[m] == m:
left = m + 1
# 否则未知的数字在 【i, m-1】
else:
right = m - 1
return left
(二) 数学法
利用等差数列前n项和来解题（差值为1）
如果不缺那个数字的话，这个数组的所有数字可以组成一个等差数列，只需要根据公式
求和，然后再减去数组中所有的数字即可
class Solution:
def solve(self , a ):
# write code here
# 0-n的数据长度
length = len(a) + 1
# 使用数学法，根据前n项和计算
return (length - 1) * length // 2 - sum(a)
时间复杂度O(n)：表示数组的长度，sum求和时间
空间复杂的O(1)：仅使用常数级变量空间
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99763.html
