【二分查找】Leetcode 点名

题目解析

LCR 173. 点名

算法讲解

1. 哈希表

class Solution {
public:int takeAttendance(vector<int>& nums) {map<int, int> Hash;for(auto n : nums) Hash[n]++;for(int i = 0; i <= nums[nums.size() - 1]; i++){if(Hash[i] == 0)return i;}return nums.size();}
};

2. 顺序遍历

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

3.位运算

class Solution {
public:int takeAttendance(vector<int>& nums) {int ret = 0;for(int i = 0; i < nums.size(); i++){ret ^= (nums[i] ^ (i+1));}return ret;}
};

二分法

class Solution {
public:int takeAttendance(vector<int>& nums) {//前半部分 nums[mid] == mid  后半部分 nums[mid] != midint left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] == mid)left = mid + 1;else right = mid;}if(nums[left] != left)return left;return left + 1;}
};