【二分查找】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] != mid
        int 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;
    }
};