算法设计与分析—0～n-1中缺失的数字题目描述：算法实现：

106 阅读 0 评论 70 点赞

我是靠谱客的博主敏感玫瑰，这篇文章主要介绍算法设计与分析—0～n-1中缺失的数字题目描述：算法实现：，现在分享给大家，希望可以做个参考。

题目描述：

0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1：
输入: [0,1,3]
输出: 2

例 2：
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

来源：力扣（LeetCode）

算法实现：

解题思路
方法一：采用set集合
1、将循环遍历，每次循环先判断该数是否在set集合中，不在则存入集合，否则返回该数

复制代码

1
2
3
4
5
6
7
8
9
10
11
# 方法一
def missingNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    for i in range(len(nums)):
        if nums[i]!=i:
            return i
    return len(nums)

方法二：二分法查找
碰到有序数组首先要想到二分法
1、如果nums[mid]==mid 说明缺少的数在 mid+1 ~ right之间，另left=mid+1
否则在 left~ mid-1 之间，另right=mid-1
2、left<=right 循环查找，跳出后返回left

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
# 方法一
def missingNumber(self, nums):
    left=0
    right=len(nums)-1
    while left<=right:
        mid=(left+right)//2
        if nums[mid]==mid:
            left=mid+1
        else:
            right=mid-1
    return left