模块三：二分——LCR. 173.点名

本文主要是介绍模块三：二分——LCR. 173.点名，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

题目链接：LCR. 173.点名

关于这道题中，时间复杂度为 O(N) 的解法有很多种，⽽且也是⽐较好想的，这⾥就不再赘述。本题只讲解⼀个最优的⼆分法和一个暴力版本，来解决这个问题。

算法原理

暴力查找

遍历一遍数组，寻找records[i] != i的位置，返回下标i即可，循环结束还没有返回结果就是数组的长度了。

二分查找

在这个升序的数组中，我们发现：

• 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
• 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。

因此，我们可以利⽤这个「⼆段性」，来使⽤「⼆分查找」算法。
PS：这里有个细节问题是当答案为数组长度时，即只有两个数时，根据判断条件left会等于records[right]，这个答案显然是错误的，所以需要处理一下。

代码实现

暴力查找

class Solution {
public:int takeAttendance(vector<int>& records) {for(int i = 0;i < records.size();i++){if(records[i] != i)return i;}return records.size();}
};

二分：C++

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0,right = records.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid)left = mid + 1;else right = mid;}//处理细节问题return (records[left] == left) ? left + 1 : left;}
};

Java

class Solution {public int missingNumber(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] == mid)left = mid + 1;elseright = mid;}return left == nums[left] ? left + 1 : left;}
}

这篇关于模块三：二分——LCR. 173.点名的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---