golang刷leetcode 技巧（20）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)-1
if 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)-1
for i,v:=range nums{
    if i^v!=0{
        return i
    }
}
return l+1
}