站长工具综合查询系统,网页的创新型网站策划,房子装修风格大全2021新款,营销型网站建设论文最长连续序列
一、题目概述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 原题地址#xff1a;https://leetcode.cn/problems/l…最长连续序列
一、题目概述
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 原题地址https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-100-liked 解题说明官方说的很清楚了我这里只对代码中的细节做一下笔记。 class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint num_set;for(const int i : nums){num_set.insert(i);} int longest 0;for(const int i : nums){if(!num_set.count(i - 1)){int currentNum i;int currentLen 1;while(num_set.count(currentNum 1)){currentLen 1;currentNum 1;}longest max (longest,currentLen);}}return longest;}};二、 unordered_set说明
在 C 中std::unordered_set 是一个非常有用的容器它是标准模板库STL的一部分。std::unordered_set 提供了一种方式来存储唯一元素的集合其内部实现基于哈希表。由于哈希表的特性std::unordered_set 在很多方面与 std::set 相区别尤其是在性能和存储组织方面。 一主要特性和用途
唯一性
与 std::set 一样unordered_set 中的每个元素都必须是唯一的。
无序
不同于基于红黑树的 std::setunordered_set 中的元素是无序存储的。这意味着你不能依赖于元素的任何排序。
哈希表实现
unordered_set 使用哈希表来存储元素。因此它的性能对于哈希函数的质量非常敏感。
二性能特点
平均时间复杂度
插入操作O(1)。在最佳情况下向 unordered_set 插入一个新元素的时间复杂度是常数级的。查找操作O(1)。查找元素的平均时间复杂度也是常数级的这是哈希表的一个显著优势。删除操作O(1)。删除特定元素的平均时间复杂度同样是常数级的。
最坏情况时间复杂度
在最坏的情况下例如所有元素都映射到同一个哈希桶中这些操作的时间复杂度会退化到 O(n)。
三使用场景
当你需要快速查找、插入和删除元素并且不关心元素的顺序时unordered_set 是一个很好的选择。适用于需要唯一元素集合的场景但与 std::set 不同它不提供任何排序保证。
三、使用 const 和引用符号 在 for 循环中有特定的目的和优势
一使用 const
const 关键字用于指定变量的值是不可修改的。 在这个上下文中它表示 num 是一个不可变的引用。这是一个良好的编程实践尤其是在遍历容器而不需要修改元素的情况下因为它可以防止在循环内部意外修改元素的值。
二使用引用符号 引用符号 用于创建一个变量的引用而不是拷贝。在这段代码中num 是 nums 集合中每个元素的引用。这意味着循环在迭代过程中不会创建 nums 中元素的副本从而提高了效率尤其是在遍历大型对象或容器时。 如果不使用引用即不使用 循环会为 nums 集合中的每个元素创建一个副本这会增加额外的内存和性能开销。对于基本数据类型如 int这种开销可能微不足道但对于大型或复杂的对象类型使用引用可以显著提高效率。 for (const int num : nums) 这种写法是一种高效且安全的迭代方式它确保了循环过程中不会意外修改集合元素同时避免了不必要的复制提升了性能。这是一种符合 C 最佳实践的写法。 道阻且行未来可期。
