【刷题日记】剑指 Offer 53 - II. 0～n-1中缺失的数字
本次刷题日记的第 22 篇，力扣题为：剑指 Offer 53 - II. 0～n-1中缺失的数字 ，简单
一、题目描述：
从深圳回到广州，现在疫情没有顺风车可以打，我那被偷走的四个小时都跑哪去了
但还是会保持良好的学习和记录习惯，毕竟养成一个良好的习惯是非常不容易的，就像锻炼身体一样
今天是一个简单题，题目相对会比较明确，可能我们会第一时间想到解决方式，但我们要明白肯定不会那么简单
二、这道题考察了什么思想？你的思路是什么？
咱还是需要来走走做题的流程，这个是必须的，是不能被跳过的，因为只有我们在思维上已经尽可能多的考虑和设计好了，那么实现上才能尽可能的偏差小
我们看看这题给我们暴露了哪些信息：
- 题中给出的数组是一个有序的，并且一定是从 0 开始的数组的最大值是 10000
- 很明确的问题，需要我们找出这个有序数组中缺失的元素，按照题目给出的意思，这个确实的元素只会是有 1 个，不会是多个
- 最终我们需要输出这个缺失的数字具体是哪个
还是老规矩，知道题中给出的重要信息之后，我们就来模拟一下就可以很清晰的明白整个思路了
首先，咱们使用傻瓜式从头遍历的方式来查找缺失的元素肯定是可以找出来的，这个没有问题， 但是时间复杂度会比较高，最高的时候，可以达到 10000 次
我们来选择推演另外一个方式，这个方式也是比较好理解的
我们可以采用这种二分的方式来查找，而不是使用最开始讲到的通过遍历去查找他
如上述例子：0-9 中，缺失 5 这个数字，那么我们使用二分查找的时候
- 确认当前的左边界 和 右边界，计算出当前的中间索引对应的值
- 校验当前中间索引对应的值是否应该是当前位置应该出现的值，例如 nums[5] 的位置就应该出现的 是 5 而不是 6
- 如果校验到当前中间索引对应的值小于应该有的值，那么说明需要往左找，是左边缺失值了，反之亦然
- 最终，当左边界和右边界相等或者左边界超过右边界的时候，咱们的需要找的值就是 左边界对应的值了
思路有了之后，接下来就是按照思路来实现想法了
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要注意控制需要在左边边界小于右边界的时候进行逻辑计算
编码如下：
func missingNumber(nums []int) int { // 本题默认是从 0 开始，我们初始化左边边界 left := 0 // 初始化右边边界为数组的长度 right := len(nums) // 任意初始化一个 中间节点 mid := 0 for left < right { // 计算中间位置 mid = (left + right) /2 // 我们知道 nums 是有序的，如果取中间位置的值是不能与中间应该存在的值，那么说明左边缺失值了 if nums[mid] != mid { right = mid }else{ // 否则就是右边缺失值了 left = mid + 1 } } return left }
根据上述编码的话，应该就很清晰了，主要是要分清具体缺失的数字应该是在左边还是右边
四、总结：
本次题目的时间复杂度是 O(logn) ,空间复杂度是 O(1)，因为我们引入了常熟级别的空间消耗
原题地址：剑指 Offer 53 - II. 0～n-1中缺失的数字
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
