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

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

创新互联建站专注于企业营销型网站建设、网站重做改版、宝鸡网站定制设计、自适应品牌网站建设、HTML5建站成都商城网站开发、集团公司官网建设、外贸营销网站建设、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为宝鸡等各大城市提供网站开发制作服务。

一个长度为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中缺失的数字这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


当前标题:leetcode怎么找到0~n-1中缺失的数字
本文URL:http://pwwzsj.com/article/jphhoi.html