leetcode怎么找到0～n-1中缺失的数字

这篇文章主要讲解了“leetcode怎么找到0～n-1中缺失的数字”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“leetcode怎么找到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

解题思路

解法1:二分

1，这是一个二分查找的变形

2，有个特殊点需要注意

3，如果 数组中，没有缺失的，那么缺失的在末尾

4，如果中间位置值和下标相等，则不用查找左边。

解法二:异或

^= 位逻辑异或赋值，是一个复合赋值运算符

异或就是两个数的二进制形式，按位对比，相同则取0。

0^0→0 , 0^1→1 , 1^0→1 , 1^1→0

任何数与0异或等于它本身，即a^0=a

一个数与自己异或结果为0，即a^a=0

令0~n的数与nums中的数异或，运算中除了缺失值只出现一次外，其他数都出现两次等同于与自身异或。

源码实现

func missingNumber(nums []int) int {l:=len(nums)-1if nums[l]==l{    return l+1} return missing(nums,0,len(nums)-1) }
func missing(nums []int,l,r int)int{ if l==r{     return l } m:=(l+r)/2  if nums[m]==m{     return missing(nums,m+1,r) } return missing(nums,l,m)}

func missingNumber(nums []int) int {l:=len(nums)-1for i,v:=range nums{    if i^v!=0{        return i    }}return l+1}

感谢各位的阅读，以上就是“leetcode怎么找到0～n-1中缺失的数字”的内容了，经过本文的学习后，相信大家对leetcode怎么找到0～n-1中缺失的数字这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！