题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例:
输入: [0,1,3]
输出: 2
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
python代码
class Solution:
def missingNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
if nums[i]!=i:
return i
return len(nums)
上述解法非常常规,根据题意,数组中的每个值应该等于它的索引值,所以直接遍历整个数组,当发现值不等于索引值时,就说明遇到了缺失值,另外要注意:当遍历结束后,仍没有找到缺失值,则说明缺失值为n。
优化
其实优化的方法也很直接,因为数组为有序数组,且题目涉及到找值,一般情况下都可以使用二分查找法,只不过我们这里的目标值变成了当前值的索引值。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
left=0
right=len(nums)-1
if nums[-1]==len(nums)-1:
return len(nums)
while left<=right:
mid = (left+right)//2
if nums[mid]==mid:
left = mid+1
else:
right = mid-1
return left