心悦做宠物的网站,中企动力科技股份,网页设计 收费,wordpress栏目页打不开学习笔记#xff1a;1.什么叫时间复杂度#xff0c;怎么算#xff1f;答#xff1a;算法执行的「基本操作次数」的「量级」 —— 简单说#xff0c;就是衡量算法 “要做多少活”#xff0c;只看 “工作量的大趋势”举个生活例子#xff1a;你数 10 个苹果#xff0c;需…学习笔记1.什么叫时间复杂度怎么算答算法执行的「基本操作次数」的「量级」—— 简单说就是衡量算法 “要做多少活”只看 “工作量的大趋势”举个生活例子你数 10 个苹果需要数 10 次数 100 个苹果需要数 100 次 → 工作量和苹果数量「成正比」时间复杂度就是O(n)你给 10 个苹果两两配对比如比较大小需要比 45 次给 100 个苹果配对需要比 4950 次 → 工作量和苹果数量的「平方成正比」时间复杂度就是O(n²)你找字典里的 “张” 字不用从头翻按拼音直接找 → 工作量和字典厚度「没关系」时间复杂度就是O(1)。核心特点只看「最高阶、最影响工作量的部分」比如n² n 10只保留n²记为O(n²)忽略「常数、系数、低阶项」比如2n简化为n记O(n)n 26简化为n记O(n)常见时间复杂度排序2.什么叫哈希集合哈希集合C 里的unordered_set是一种「只存值、不存键」的哈希表结构。此题思路1.传统的暴力枚举 一个一个问x x1 x2..是否存在 虽然是最直观最简单的方法但是需要一个一个问。比如数组[1,2,3,4]遍历到1时会找2、3、4长度 4遍历到2时又会找3、4长度 3遍历到3找4长度 2遍历到4啥也找不到长度 1。这样最坏的情况下时间复杂度就是On方不满足条件。2.优化思路当这个数是连续序列的起点的时候我们再开始找后续的序列。否则不找。即看x-1存不存在。这样比如数组[1,2,3,4]对1来说x-10不存在x1 x2 x3 x4存在记下这个连续序列的长度为4.对2、3、4来说前一个数都存在不记录。直接只需遍历1次时间复杂度为on。3.工具选择--哈希集合-无序效率高4.完整思路把数组中的所有数放到哈希表中遍历哈希集合里的每个数num如果num-1不在集合里说明num是连续序列的起点从num开始依次找num1、num2... 直到找不到为止记录当前序列长度更新「最长序列长度」如果num-1在集合里说明num不是起点直接跳过不做任何计算最后返回最长序列长度。class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint num_set; //创建一个哈希集合unorderd_set //把数据存放到哈希集合中 for(const intnum : nums){//新版循环来遍历这个数组nums其中用的是常量引用num const表示不修改num表示引用避免拷贝 num_set.insert(num); // 插入数到集合中自动去重比如数组有重复的0也只存一个 } //设置初始最长序列 int longestStreak 0; //遍历刚才存好的哈希集合 for(const int num : num_set){ if(!num_set.count(num -1)){ //如果在这个哈希集合中num-1不存在 判断num-1是否在集合里存在返回1不存在返回0 int currentNum num; //那么当且的起始数就为该数 int currentStreak 1;//序列此刻就在这里开始计数 while(num_set.count(currentNum 1)){ //循环条件为该数的下一个数存在 当没有下一个数的时候停止 currentNum 1; currentStreak 1; } longestStreak max(longestStreak,currentStreak);//应对数组有多个连续序列 } } return longestStreak; } };