本文主要是介绍二分算法8️⃣-0~n-1 中缺失的数字(easy),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:LCR 173. 点名
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组
records
。假定仅有一位同学缺席,请返回他的学号。示例 1:
输入: records = [0,1,2,3,5] 输出: 4示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7提示:
1 <= records.length <= 10000
解法(二分查找算法):
算法思路:
关于这道题中,时间复杂度O(N) 的解法有很多种,而且也是比较好想的,这里就不再赘述。本题只讲解一个最优的二分法,来解决这个问题。
在这个升序的数组中,我们发现:
▪ 在第一个缺失位置的左边,数组内的元素都是与数组的下标相等的;
▪ 在第一个缺失位置的右边,数组内的元素与数组下标是不相等的。
因此,我们可以利用这个「二段性」,来使用「二分查找」算法。
class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0,right = records.size();while(left < right){int mid = left + (right - left)/2;if(records[mid] == mid) left = mid + 1;else right = mid;}return left;}
};
这篇关于二分算法8️⃣-0~n-1 中缺失的数字(easy)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!