题目来源:牛客网
描述
从 0,1,2,...,n 这 n+1 个数中选择 n 个数,选择出的数字依然保持有序,找出这 n 个数中缺失的那个数,要求 O(n) 或 O(log(n)) 并尽可能小。
示例1
输入:[0,1,2,3,4,5,7]
返回值:6
示例2
输入:[0,2,3]
返回值:1
解题思路
1、找一个递增的数值分别跟列表中的每一个值进行比对,如果不想等则返回这个值
3、如果都想等,则返回列表最后一个元素的下一个值
class Solution:
def solve(self , a ):
# write code here
n = 0
while True:
if a[n] != n:
return n
if a[n] == a[-1]:
return n+1
n = n +1
当然还有其他的思路:
1、新建一个完整数字列表,然后将两个列表都进行求和(用列表的sum
函数即可对整个列表求和),取差值。
2、如果差值为0,则返回列表最后一个元素的下一个制。
这里就不上代码了,大家可以实际尝试下,看看哪一个运行效率比较高