个人评价：数组下标还是很有用的~ 暴力解法优化至经典二分查找，作为基础算法题入门不错的~
题目难度：🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
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
解题思路
方法一
暴力法结合题目条件 「0～n-1 + 长度为n-1的递增排序数组」，不难想到下标和数值是==的
Go 示例参考如下：
func missingNumber(nums []int) int {
for i, v := range nums {
if i != v {
return i
}
}
return len(nums)
}
复杂度？🙌 O(n)
方法二
继续优化，排序数组查找的优化不难想到使用二分法，思路如下：
func missingNumber(nums []int) int {
left := 0
right := len(nums)
for left < right {
mid := (left + right) >> 1 //相当于除2
if nums[mid] != mid { //nums是有序数组，如果mid和数字不相同就在左边查找
right = mid
} else { //mid和数字相同，缺失的数字在右边，left向上取整+1
left = mid + 1
}
}
return left
}
复杂度？🙌 O(logn)
方法三
利用总和差值，联想到奥数题啊哈哈，🐂
- 计算当数组不缺数字时的总和 count
- count减去该数组nums的总和
- 得到的差值即是缺失的数字
方法四
记录数字，利用数组中数字与数组的索引相同
- 申请一个长度为 len(nums)+1 的 bool 数组 flag
- 遍历 nums 数组并记录数字在 flag 数组中对应的索引的值为 true
- 再遍历一次 flag 数组 ，得到其中值为false的索引即为缺失的数字
总结
没想到还有方法三、四、五，全靠网友的智慧 【Golang】二分、异或、差值、标记，秀啊~
↑ 提到的异或法，我看不懂 😂
题目本身不难，面试时方法二，记得起来秀下方法三的总和差鸭~
