leetcode劍指offer53 二分查找之0~n-1缺失的數(shù)字

一個(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

文章目錄

• leetcode劍指offer53 二分查找之0~n-1缺失的數(shù)字
• 二分法一
• 二分法二

二分法一

這一題和leetcode278第一個(gè)錯(cuò)誤版本很類似leetcode278第一個(gè)錯(cuò)誤版本

public int missingNumber(int[] nums) {int left=0;int right=nums.length-1;//索引范圍在[left,right]//這邊必定要把索引[left,right]中每個(gè)都判斷一下，所以不能是<;如果是<,那就少了left==right的情況，里面有個(gè)數(shù)沒有判斷到。while(left<=right){int mid=(left+right)>>1;if(nums[mid]!=mid){//這邊是重點(diǎn),不等于為什么不直接返回，因?yàn)榭赡艽藭r(shí)的mid并不是第一個(gè)缺失的數(shù)字，所以還要往前推。right=mid-1;}else{//如果nums[mid]==mid，left必定要mid+1;這肯定沒問題left=mid+1;}}//因?yàn)樵谧詈笠粚友h(huán)，left==right，//如果nums[mid]!=mid,right=mid-1,left還是等于mid;//如果nums[mid]==mid,left=mid+1;如果還是不明白可以找個(gè)案例走下流程就懂了。return left;//這邊必定返回left}

二分法二

方法二就不給很多注釋了，和之前的幾篇二分搜索都差不多，尤其leetcode278第一個(gè)錯(cuò)誤版本很類似leetcode278第一個(gè)錯(cuò)誤版本

public int missingNumber(int[] nums) {int left=0;int right=nums.length;//left==right退出循環(huán)while(left<right){int mid=(left+right)>>1;if(nums[mid]!=mid){right=mid;//為了和[left,right)保持一致，這邊right必須等于mid}else{left=mid+1;}}return left; //返回left或者right都可以 }

總結(jié)

以上是生活随笔為你收集整理的5、leetcode剑指offer53 二分查找之0~n-1缺失的数字**的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。