网站流量 钱重庆工程建筑信息网

​

​

🔥个人主页：guoguoqiang. 🔥专栏：leetcode刷题

​
​
LeetCode :LCR 173. 点名

这个题就是缺失的数字，我们可以通过三种方式来解决这个问题。
1.可以通过位异或的方式来找到这个数（相同的数异或为0）

class Solution {
public:int takeAttendance(vector<int>& records) {int ret=0;for(auto n:records) ret^=n;//遍历整个数组for(int i=0;i<=records.size();i++){//遍历全部数ret^=i;}return ret;}
};

2.通过哈希表来实现（观察这个题中的数据可以通过使用数组来实现）

class Solution {
public:int takeAttendance(vector<int>& records) {int hash[10001]={0};for(auto ch:records) hash[ch]++;for(int i=0;i<=records.size();i++){//遍历数if(!hash[i]) return i;//如果不在哈希表中说明就是缺失的那个值。}return -1;//leetcode的检查机制}
};

3.二分查找

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;}if(records[left]!=left) return left;//缺失值在数组中间else return left+1;//缺失值在数组的最后一个位置}
};

4.暴力搜索

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

5.数学（高斯求和公式）

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