题解 | #缺失数字# -- 【Python3】
缺失数字
http://www.nowcoder.com/practice/9ce534c8132b4e189fd3130519420cde
方法1:暴力破解
- 判断数组下标和数组值是否一致
- 如果不一致,说明跳过了一个,返回下标即可
- 如果所有都一致,说明缺少最后一个,返回数组长度即可
class Solution:
def solve(self , a ):
# write code here
for i, v in enumerate(a):
if i != v:
return i
return len(a)
方法2:二分法
class Solution:
def solve(self , a ):
# write code here
n = len(a)
if n == 0:
return 0
if a[-1] + 1 == n: return n
left, right = 0, n-1
while left < right:
# int()为向下取整,//为向上取整
mid = int(left + (right - left)/2)
if a[mid] == mid:
left = mid + 1
if a[mid] > mid:
right = mid
return left
方法3:求和
- 用len()函数获取长度n
- 用range()函数产生一个0:n+1的列表b
- 对列表b和列表a分别求和
- 列表b的和 减去 列表a 的和 即为缺失值
class Solution:
def solve(self , a ):
return sum(range(len(a)+1)) - sum(a)