济南市住房与城乡建设厅网站,公司网站如何建设教程,做网站需要准备的东西,免费网站制作在线算法流程#xff1a; 哈希集合去重#xff1a; 通过将数组中的所有元素放入 unordered_set#xff0c;自动去除重复元素。集合的查找操作是 O(1)#xff0c;这为后续的快速查找提供了保证。 遍历数组#xff1a; 遍历数组中的每一个元素。对于每个元素#xff0c;首先检…
算法流程 哈希集合去重 通过将数组中的所有元素放入 unordered_set自动去除重复元素。集合的查找操作是 O(1)这为后续的快速查找提供了保证。 遍历数组 遍历数组中的每一个元素。对于每个元素首先检查它是否是某个连续序列的第一个元素。具体地如果当前元素的前一个元素 (num - 1) 不在集合中说明当前元素有可能是某个序列的开始。这是关键步骤因为如果 num - 1 在集合中说明当前元素是某个序列的中间元素不需要再处理。 序列长度统计 当确定当前元素为某个序列的起点时进入一个循环检查当前元素的后一个元素 (num 1、num 2、… ) 是否存在于集合中。利用 count() 来检查每个右邻元素是否存在如果存在则将 currentStreak 加 1 继续统计直到右邻元素不再存在。 更新最大长度 每当一个序列结束时使用 max() 函数更新全局的最大序列长度 longestStreak。
代码结构与逻辑重点
哈希集合的使用 保证了我们能够在 O(1) 时间内查找某个元素是否存在。通过判断左邻元素是否存在 确保我们只对可能的序列起点进行处理避免了对所有元素都重复计算。count() 函数的 O(1) 查找时间 确保了我们能在常数时间内判断右邻元素是否存在从而以线性时间完成整个数组的遍历和处理。
通过哈希集合的使用算法避免了排序操作O(n log n)从而保证了线性时间复杂度 O(n)。
算法思路
首先利用数组所有元素来初始化一个哈希集(unordered_set)由于集合性质这一步会自动去除重复元素。
然后我们再去遍历数组每个元素仅当当前元素是可能是某个最长连续序列的第一个元素时 (左邻元素不存在于哈希集中)我们进行序列长度统计。
所以如果当前元素的前一个相邻元素(num - 1)存在于哈希集中那么说明当前元素必然不可能是某个最长连续序列的开始元素。这种情况下我们跳过不予处理。
再回到如果当前元素的确是某个可能的最长连续序列的第一个元素时我们利用 STL 容器的成员函数 count() 来判断当前元素的右邻元素是否存在于哈希集中并使用一个新的变量(currentStreak)来统计当前最长连续序列的长度,
在 unordered_set 中count() 函数的主要作用是检查某个值是否存在于集合中。因为 unordered_set 只存储唯一的元素因此 count() 要么返回 0要么返回 1
返回 0表示该元素不在集合中。返回 1表示该元素在集合中。
如果右邻元素存在于哈希集那么currentStreak 加1如果不存在于哈希集中则直接跳出循环。
每当跳出循环时意味着最近一次处理的连续序列的长度已经统计结束需要和上一次处理的连续序列的长度(currentStreak)进行 max 对比并更新currentStreak
class Solution {
public:int longestConsecutive(vectorint nums) {//初始化一个无序集合并且将nums数组中的元素全部加入到这个集合中unordered_setint numSet(nums.begin(), nums.end());//最长序列长度int longestStreak 0;for(int num : nums) {if(numSet.count(num - 1) 0) {//如果当前元素的前一个连续元素并不存在于集合中说明当前元素有可能是一个最长连续序列的开头//并且这个最长连续序列目前至少长度为1int currentStreak 1;//然后逐个1并在集合中判断是否存在直到不存在时终止int currentNum num;while(numSet.count(currentNum 1)) {currentStreak;currentNum;}longestStreak max(longestStreak, currentStreak);}}return longestStreak;}
};
