目錄

我們直接看題解吧：

審題目+事例+提示：

方法：

解題思路（二分法）：

代碼：

方法二：直接遍歷

---

題目地址

LCR 173. 點(diǎn)名 - 力扣（LeetCode）

今天刷點(diǎn)名（缺失的數(shù)字），大家有興趣可以點(diǎn)上看看題目要求，試著做一下。

我們直接看題解吧：

審題目+事例+提示：

record為升序數(shù)組

方法：

遇到排序數(shù)組的搜索問(wèn)題，首先想到二分法

解題思路（二分法）：

依據(jù)題意，我們可以把數(shù)組分為兩部分，

?左子數(shù)組，record[i]=i

?右子數(shù)組，record[i]!=i

所以，缺失的數(shù)字其實(shí)就是右子數(shù)組的首元素。

1. 初始化i=0即左邊界,j=length-1，即右邊界
2. 循環(huán)二分：當(dāng)i<=j時(shí)跳出循環(huán)

?????·計(jì)算中點(diǎn)m=(i+j)/2(向下取整)

?????·record[m]==m,即缺失數(shù)字在[m+1,j],則i=m+1

?????·record[m]！=m，即缺失數(shù)字在[i,m-1],則j=m-1

? ? 3、最后跳出循環(huán)，i指向位置為缺失的數(shù)字

代碼：

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

---

方法二：直接遍歷

class Solution {public int missingNumber(int[] nums) {if (nums[0]==1) return 0;for (int i = 0;i<nums.length;i++){if (nums[i]!=i) return i;}return nums.length;}
}