[LC优选算法#10] 二分 | 点名

1. 点名点名解题思路这道题有很多解法但是时间复杂度基本都是O(N)哈希表遍历数组统计0~n每个元素出现的次数再次遍历找出缺失的数字。遍历数组遍历数组直至遇到下标与元素不相等的位置返回下标。位运算将数组中的元素全部异或^结果即为缺失的数字。求和求出0 ~ n的和后逐一减去数组中的元素结果即为缺失的数字。二分查找O(logN)因为数组是升序排列的这里是否可以尝试用二分算法解决呢答案是肯定的。观察发现数组中的元素和下标存在一定的联系当区间内的元素没有缺失时元素与下标是一一对应的但是在缺失元素之后的区间下标小于对应的元素。这样数组就有了二段性。显而易见二分算法的时间复杂度是最优的。//二分查找classSolution{public:inttakeAttendance(vectorintrecords){intleft0;intrightrecords.size()-1;while(leftright){intmidleft(right-left)/2;if(records[mid]mid){leftmid1;}else{rightmid;}}if(leftrecords[left])returnleft1;returnleft;}};哈希表classSolution{public:inttakeAttendance(vectorintrecords){vectorinthash(records.size()1,0);for(autox:records){hash[x];}for(inti0;ihash.size();i){if(hash[i]0){returni;}}return0;}};// 直接遍历找结果classSolution{public:inttakeAttendance(vectorintrecords){inti;for(i0;irecords.size();i){if(records[i]!i){returni;}}returni;}};//异或相同为0不同为1classSolution{public:inttakeAttendance(vectorintrecords){intret0;intnum0;for(inti0;irecords.size();i){ret^records[i];ret^num;}returnret^num;}};//求和相减classSolution{public:inttakeAttendance(vectorintrecords){intnrecords.size();intretn*(n1)/2;//注意计算公式for(autox:records){ret-x;}if(ret0records[0]!0)return0;returnret;}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~