剑指 Offer 53 – II. 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
限制：
1 <= 数组长度 <= 10000
二、题目解析
为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
public int missingNumber(int[] nums) {
// left 指向当前区间的最左边位置，所以初始化为 0
int left = 0 ;
// right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
int right = nums.length - 1;
// 循环进行二分查找，直到左端点位置超过了右端点
while( left <= right ) {
// 计算当前区间的中间位置，向下取整
int mid = (left + right) / 2;
// 如果中间位置的元素值等于当前索引的值
// 那么说明从 left 到 mid 的这些元素都在正确的位置上
// 即从 left 到 mid 的这些数字都在数组中，没有发生缺失
// 所以需要在 mid + 1 到 right 这个区间去查找缺失的数字
if(nums[mid] == mid){
// 缩小范围为 mid + 1 到 right
// 当前区间的左侧为 left = mid + 1，右侧 right
left = mid + 1;
// 否则，说明从 left 到 mid 的这些元素，有元素不在正确的位置上
// 即从 left 到 mid 的这些数字有数字发生缺失
// 所以需要在 left 到 mid - 1 这个区间去查找缺失的数字
}else{
// 所以缩小范围为 left 到 mid - 1
// 当前区间的左侧为 left，右侧 right = mid - 1
right = mid - 1;
}
}
// 由于只有一个数字缺失，所以找到的时候，left 指向的那个数字就是，使得后面所有数字与索引不一一对应时的第一个数字
// 返回就行
return left;
}
}
2、C++ 代码
class Solution {
public:
int missingNumber(vector<int>& nums) {
// left 指向当前区间的最左边位置，所以初始化为 0
int left = 0 ;
// right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
int right = nums.size() - 1;
// 循环进行二分查找，直到左端点位置超过了右端点
while( left <= right ) {
// 计算当前区间的中间位置，向下取整
int mid = (left + right) / 2;
// 如果中间位置的元素值等于当前索引的值
// 那么说明从 left 到 mid 的这些元素都在正确的位置上
// 即从 left 到 mid 的这些数字都在数组中，没有发生缺失
// 所以需要在 mid + 1 到 right 这个区间去查找缺失的数字
if(nums[mid] == mid){
// 缩小范围为 mid + 1 到 right
// 当前区间的左侧为 left = mid + 1，右侧 right
left = mid + 1;
// 否则，说明从 left 到 mid 的这些元素，有元素不在正确的位置上
// 即从 left 到 mid 的这些数字有数字发生缺失
// 所以需要在 left 到 mid - 1 这个区间去查找缺失的数字
}else{
// 所以缩小范围为 left 到 mid - 1
// 当前区间的左侧为 left，右侧 right = mid - 1
right = mid - 1;
}
}
// 由于只有一个数字缺失，所以找到的时候，left 指向的那个数字就是，使得后面所有数字与索引不一一对应时的第一个数字
// 返回就行
return left;
}
};
3、Python 代码
class Solution:
def missingNumber(self, nums: List[int]) -> int:
# left 指向当前区间的最左边位置，所以初始化为 0
left = 0
# right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
right = len(nums)- 1
# 循环进行二分查找，直到左端点位置超过了右端点
while left <= right :
# 计算当前区间的中间位置，向下取整
mid = (left + right) // 2
# 如果中间位置的元素值等于当前索引的值
# 那么说明从 left 到 mid 的这些元素都在正确的位置上
# 即从 left 到 mid 的这些数字都在数组中，没有发生缺失
# 所以需要在 mid + 1 到 right 这个区间去查找缺失的数字
if nums[mid] == mid :
# 缩小范围为 mid + 1 到 right
# 当前区间的左侧为 left = mid + 1，右侧 right
left = mid + 1
# 否则，说明从 left 到 mid 的这些元素，有元素不在正确的位置上
# 即从 left 到 mid 的这些数字有数字发生缺失
# 所以需要在 left 到 mid - 1 这个区间去查找缺失的数字
else:
# 所以缩小范围为 left 到 mid - 1
# 当前区间的左侧为 left，右侧 right = mid - 1
right = mid - 1
# 由于只有一个数字缺失，所以找到的时候，left 指向的那个数字就是，使得后面所有数字与索引不一一对应时的第一个数字
# 返回就行
return left
