題目

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

示例 1:

輸入: [0,1,3] 輸出: 2 示例?2:

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

分析這道題的題目

這道題目的本質(zhì)：小夕認(rèn)為是需要讀懂題目。小夕一開始也沒被整懵了，后來想了想原來是這么回事：

這道題題目本質(zhì)是找到第一個(gè)數(shù)組下標(biāo)和數(shù)組中的數(shù)不匹配的，如下圖中的例子，是數(shù)組下標(biāo)為4的時(shí)候，數(shù)組中的數(shù)應(yīng)該是4。

為什么是這樣子呢？

閱讀題目，數(shù)組是單調(diào)遞增的，而且數(shù)字是無重復(fù)的，所以缺失一個(gè)數(shù)字的話，就導(dǎo)致數(shù)組的下標(biāo)和數(shù)組的數(shù)字沒對應(yīng)上。
如數(shù)組下標(biāo)4，而且從數(shù)組下標(biāo)4開始到之后的所有的數(shù)組下標(biāo)（4/5/6）中的數(shù)（數(shù)組中的5/6/7 ）都沒有和數(shù)組下標(biāo)對齊。
所以現(xiàn)在我們知道了數(shù)組是上圖中的這個(gè)樣子，知道了數(shù)組是這個(gè)樣子，那我們就簡單了呀~

暴力解法

暴力解法圖解

暴力動(dòng)畫

代碼

class?Solution?{
????public?int?missingNumber(int[]?nums)?{

????????for(int?i?=?0;?i?????????????if(nums[i]?!=?i)?{
????????????????return?i;
????????????}
????????}
????????return?nums.length;
????}
}

二分查找

由于是排序數(shù)組，肯定會(huì)想到二分查找：

1.首先數(shù)組里的元素都是固定的，我們只需要通過二分查找確定缺失的元素是在左邊還是右邊。
2.老樣子 left = 0 和 right = nums.length -1
3.我們先通過計(jì)算獲取到中位數(shù)int mid = left + (right -left) / 2
4.判斷nums[mid] == mid 雖然數(shù)組元素是缺失的但是下標(biāo)是完整，如果 nums[mid] == mid 說明缺失的元素在右邊，否則相反。
5.當(dāng)我們判斷缺失的元素在右邊時(shí)候，這時(shí)候區(qū)間就是[mid + 1,right];
6.當(dāng)我們判斷缺失的元素在左邊時(shí)候，這時(shí)候區(qū)間就是[left,mid - 1];
7.當(dāng)left指向了右邊數(shù)組的第一個(gè)元素 right指向了做數(shù)組的最后一個(gè)元素則直接返回left。

為了更好的理解，圖解看一下：

圖解

二分查找動(dòng)畫

代碼

Java

class?Solution?{
????public?int?missingNumber(int[]?nums)?{
????????int?i?=?0,?j?=?nums.length?-?1;
????????while(i?<=?j)?{
????????????int?m?=?(i?+?j)?/?2;
????????????if(nums[m]?==?m)?i?=?m?+?1;
????????????else?j?=?m?-?1;
????????}
????????return?i;
????}
}

C++

class?Solution?{
public:
????int?missingNumber(vector&?nums)?{
????????int?left?=?0,?right?=?nums.size();??//使用左閉右開區(qū)間
????????while(left?????????{
????????????int?mid?=?(right?-?left)/2?+?left;
????????????if(nums[mid]?!=?mid)??right?=?mid;??
????????????if(nums[mid]?==?mid)??left??=?mid+1;???
????????}
????????return?left;
????}
};

JS

/**
?*?@param?{number[]}?nums
?*?@return?{number}
?*/
var?missingNumber?=?function(nums)?{
????//?左指針
????let?leftI?=?0
????//?右指針
????let?rightI?=?nums.length
????//?中間指針
????let?midI?
????//?以?leftI?????while(leftI?<=?rightI){
????????midI?=?Math.floor((leftI?+?rightI)/2)
????????//?如果?nums[midI]?===?midI?說明想尋找的數(shù)在?midI?右方
????????nums[midI]?===?midI???leftI?=?midI?+?1?:?rightI?=?midI?-?1
????}
????return?leftI
};

Python

class?Solution:
????def?missingNumber(self,?nums:?List[int])?->?int:
????????i,?j?=?0,?len(nums)?-?1
????????while?i?<=?j:
????????????m?=?(i?+?j)?//?2
????????????if?nums[m]?==?m:?i?=?m?+?1
????????????else:?j?=?m?-?1
????????return?i

一道頭條面試題，差點(diǎn)沒讀懂題目，找出數(shù)組中缺失的數(shù)字,最近擊敗100%的用戶！

題目