這篇文章主要講解了“l(fā)eetcode怎么找到0～n-1中缺失的數(shù)字”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“l(fā)eetcode怎么找到0～n-1中缺失的數(shù)字”吧！

創(chuàng)新互聯(lián)建站專注于企業(yè)營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、網(wǎng)站重做改版、寶雞網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5建站、成都商城網(wǎng)站開(kāi)發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為寶雞等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。

一個(gè)長(zhǎng)度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的，并且每個(gè)數(shù)字都在范圍0～n-1之內(nèi)。在范圍0～n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中，請(qǐng)找出這個(gè)數(shù)字。

示例 1:

輸入: [0,1,3]

輸出: 2

示例 2:

輸入: [0,1,2,3,4,5,6,7,9]

輸出: 8

限制：

1 <= 數(shù)組長(zhǎng)度 <= 10000

解題思路

解法1:二分

1，這是一個(gè)二分查找的變形

2，有個(gè)特殊點(diǎn)需要注意

3，如果 數(shù)組中，沒(méi)有缺失的，那么缺失的在末尾

4，如果中間位置值和下標(biāo)相等，則不用查找左邊。

解法二:異或

^= 位邏輯異或賦值，是一個(gè)復(fù)合賦值運(yùn)算符

異或就是兩個(gè)數(shù)的二進(jìn)制形式，按位對(duì)比，相同則取0。

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

任何數(shù)與0異或等于它本身，即a^0=a

一個(gè)數(shù)與自己異或結(jié)果為0，即a^a=0

令0~n的數(shù)與nums中的數(shù)異或，運(yùn)算中除了缺失值只出現(xiàn)一次外，其他數(shù)都出現(xiàn)兩次等同于與自身異或。

源碼實(shí)現(xiàn)

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}

感謝各位的閱讀，以上就是“l(fā)eetcode怎么找到0～n-1中缺失的數(shù)字”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)leetcode怎么找到0～n-1中缺失的數(shù)字這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！