問(wèn)題描述:
給出從0到n的n+1個(gè)數(shù)字中的n個(gè)數(shù)，找到缺失的那個(gè)數(shù)字
注意：給定的數(shù)組并不一定是有序的數(shù)組
Paste_Image.png
代碼示例一：時(shí)間復(fù)雜度較高,因?yàn)橄葘?duì)數(shù)組進(jìn)行了排序
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
n = len(nums)
if nums[0] != 0: return 0
for i in range(1,n):
if nums[i] != nums[i-1] + 1:
return i
return n
代碼示例二：根據(jù)數(shù)學(xué)知識(shí)進(jìn)行求解，0,1,2,,,n等差數(shù)列求和 - 數(shù)組的總和 即為缺失的那個(gè)數(shù)字
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
sum_n = n*(n+1)/2 #等差數(shù)列求和
return sum_n - sum(nums)
