大家好,我是吴师兄。
今天给大家分享的 LeetCode 的评论来源于 LeetCode 上的剑指 Offer 53 号问题0~n-1中缺失的数字的评论区。
这个评论并没有给出什么骚话,不过很有道理,我们的解题代码得用上题目给出的每个条件才是一个好的解题代码。
首先给没有见过这道题目的小伙伴补充一下前置知识,这道题目讲的是:
一个长度为 n – 1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n – 1 之内。
在范围 0 ~ n – 1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。
比如数组为 [0,1,2,3,4,5,6,7,9]
,注意到 8 不在里面,因此输出 8 。
如果在面试的时候拿到这个题目,交出的代码是遍历的方式,那真的就和评论区的老哥留言的那样:
所有题都拿来遍历,offer也就遍历到别人那里去了。
面试官看到你提交的代码,会笑呵呵的让你回去等通知,好一点的会问你能不能再优化一下。
很明显,遍历的方式没有用到题目给出的所有条件:
- 所有数字都是唯一的
- 每个数字都在范围 0 ~ n – 1 之内
- 有且只有一个数字不在该数组中
这里给大家一个小技巧,但凡看到数组、搜索相关的词语,第一想法可以去尝试二分法。
如果每一个数字都出现正确的位置上,即它们和索引之间的对应关系都是一样的,比如数字 0 出现在索引位置为 0 的地方、数字 1 出现在索引位置为 1 的地方、数字 2 出现在索引位置为 2 的地方。。。
而如果发现有数字没有出现在正确的位置上,也就是发生了错位,比如数字 9 出现在索引位置为 8 的地方,那么由于有且只有一个数字不在该数组中,那么很明显数字 10 出现在索引位置为 9 的地方、数字 11 出现在索引位置为 10 的地方。。。
我们只需要找到第一个发生了错位的地方就可以了。
也就是说,原来的整个数组实际上是包含了两个部分。
-
1、一个部分上面所有的数字都在正确的位置上;
-
2、另外一部分上面所有的数字都不在正确的位置上
那么就利用二分法的思路,不断的缩小查找区间,也就能找到第一个发生了错位的数字。
这里直接给出代码:
// 登录 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;
}
}