网站建设制作模板网站怎么做_网红营销的弊端_安卓手机优化软件哪个好_互联网推广方式有哪些

目录

一：题目

二：算法原理分析

三：代码实现

---

一：题目

题目链接： LCR 173. 点名 - 力扣（LeetCode）

二：算法原理分析

三：代码实现

二分查找版：

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;elseright = mid;}    if(records[left] == left)return left+1;elsereturn left;}
};

哈希表版：

class Solution {
public:int takeAttendance(vector<int>& records) {int len = records.size()+1;int hash[10000] = {0};for(auto& e : records){hash[e]++;}for(int i = 0; i<=records.size();i++){if(hash[i] == 0)return i;}return 0;}
};

直接遍历版：

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

数学方法：

class Solution {
public:int takeAttendance(vector<int>& records) {int length = records.size();int sum = (0 + length) * (length + 1) / 2;for(auto e : records){sum -= e;}return sum;}
};

位运算：

class Solution {
public:int takeAttendance(vector<int>& records){int x = 0;for(int i = 0; i <= records.size();i++)x ^= i;  for(auto& e : records)x ^= e;return x;}
};