传送门

思路：

解法 1 ：

$\quad$等差数列求和之后，将存在的$id$扣掉，那么总和最后就是剩下的哪个

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

时间复杂度 $O(N)$

解法 2：

$\quad$当一个数消失后，其后面的数会补充上来，形成错位$nums[i]!=i$，而前边都是$nums[i]=i$，这样我们就可以二分左边界，$nums[i]!=i$，其中的i就是消失的数

class Solution {
public:
    int takeAttendance(vector<int>& record) {
        int l=0,r=(int)record.size();
        while(l<r)
        {
             int mid=l+r>>1;
             if(record[mid]!=mid)r=mid;
             else l=mid+1;
        }
        return l;
    }
};

时间复杂度 $O(\log N )$