题解：点名(暴力求解 + 哈希表 + 数学方法 + 位运算 + 二分算法)，有需要借鉴即可。
1.题目
题目链接：LINK
这个题目有很多种解法。下面我不再细说，直接摆代码。
class Solution { public: //方法一：直接求解，暴力求解 // int takeAttendance(vector<int>& records) // { // for(size_t i = 0; i < records.size(); i++) // { // if(records[i] != i)return i; // } // return records.size();//最后一个数字缺失 // } //方法二：哈希数组 // int takeAttendance(vector<int>& records) // { // int arr[10000] = {0}; // for(size_t i = 0; i < records.size(); i++) // { // arr[records[i]]++; // } // for(size_t i = 0; i < records.size(); i++) // { // if(arr[i] == 0) return i; // } // return records.size(); // } //方法三：数学方法 // int takeAttendance(vector<int>& records) // { // int sum_i = 0; // sum_i = (0 + records.size())*(records.size()+1) / 2; // for(int i = 0; i < records.size(); i++) // { // sum_i -= records[i]; // } // return sum_i; // } //方法四：位运算 // int takeAttendance(vector<int>& records) // { // int ret = 0; // for(size_t i = 0; i < records.size() + 1; i++) // { // if(i != records.size()) // ret^=records[i]; // ret^=i; // } // return ret; // } //方法五：二分算法 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; } //特殊情况 return left == records[left] ? left + 1 : left; //if(records[left] == left) return left+1; //return left; } };
2.总结
这算个十分简单的题目，可以采用多种方法进行解答。
倘若对上面代码存在疑问，可以评论(或者私信)留下你的疑问。
EOF
