溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“l(fā)eetcode怎么找到0～n-1中缺失的數(shù)字”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“l(fā)eetcode怎么找到0～n-1中缺失的數(shù)字”吧！
一個長度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的，并且每個數(shù)字都在范圍0～n-1之內(nèi)。在范圍0～n-1內(nèi)的n個數(shù)字中有且只有一個數(shù)字不在該數(shù)組中，請找出這個數(shù)字。
示例 1:
輸入: [0,1,3]
輸出: 2
示例 2:
輸入: [0,1,2,3,4,5,6,7,9]
輸出: 8
限制：
1 <= 數(shù)組長度 <= 10000
解題思路
解法1:二分
1，這是一個二分查找的變形
2，有個特殊點需要注意
3，如果 數(shù)組中，沒有缺失的，那么缺失的在末尾
4，如果中間位置值和下標相等，則不用查找左邊。
解法二:異或
^= 位邏輯異或賦值，是一個復合賦值運算符
異或就是兩個數(shù)的二進制形式，按位對比，相同則取0。
0^0→0 , 0^1→1 , 1^0→1 , 1^1→0
任何數(shù)與0異或等于它本身，即a^0=a
一個數(shù)與自己異或結(jié)果為0，即a^a=0
令0~n的數(shù)與nums中的數(shù)異或，運算中除了缺失值只出現(xiàn)一次外，其他數(shù)都出現(xiàn)兩次等同于與自身異或。
源碼實現(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)/2if 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)過本文的學習后，相信大家對leetcode怎么找到0～n-1中缺失的數(shù)字這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
