wap网站制作方案,网站名字 备案,做网站开发所需的知识技能,浙江做网站公司排名128. 最长连续序列 乍一看感觉很简单#xff0c;一看要用O(n)??? 因为我觉得题目很难而且题目看起来很简单#xff0c;感觉以后会用到#x1f606;#xff0c;做个记录
1.朴素做法
思路 答:任何一段连续的数都有一个左端点#xff1a;比如#xff08;1#xff0c;…128. 最长连续序列 乍一看感觉很简单一看要用O(n)??? 因为我觉得题目很难而且题目看起来很简单感觉以后会用到做个记录
1.朴素做法
思路 答:任何一段连续的数都有一个左端点比如1234的左端点是1且找到1之后发现1234为最长的连续区间那么从234为左端点的区间都不需要继续尝试了因为他们都比1为左端点的区间短。 那么我们只需要找所有的左端点然后不停比较更新即可。 怎么找左端点只要没有比它更小的数那么就是左端点比如[100,1,3,2,4],这个数组有两个左端点1001。用哈希表空间换时间这样就不需要每次找到一个数然后去for循环判断有没有比他小的数以及他后面接着几个连续的数
class Solution
{
public:int longestConsecutive(vectorint nums) {int nnums.size();unordered_setintHash; //set只有一个参数然后去重重复的键值不会被插入for(int i0;in;i)Hash.insert(nums[i]);int ans0;for(int i0;in;i){if(Hash.find(nums[i]-1)!Hash.end())//num[i]-1存在nums[i]不是左端点continue;else{int xnums[i]1; //nums[i]是左端点从x开始尝试找int len1;while(Hash.find(x)!Hash.end()){x;len;}ansmax(ans,len);}}return ans;}
};2.并查集
思路 将连接在一起的数放在一个集合且这个集合的根节点是当前集合最大的数 这里也用到左端点的思路而且优化了并查集一步到位。
class Solution {
public:unordered_mapint,int a;int find(int x) //找到该元素集合的根节点路径压缩{if(a.count(x)){a[x]find(a[x]);return a[x];}elsereturn x;//return a.count(x)?a[x]find(a[x]):x;}int longestConsecutive(vectorint nums) {for(auto i:nums) //这一步很巧妙这个错位的赋值使find函数一步到位只要使连续的那么就把所有连续的数都放在集合里了。a[i]i1;int ans0;for(auto i:nums){int yfind(i1);ansmax(ans,y-i);}return ans;}
};
3.动态规划
思路 最终求的是最长的连续数组那么可以把解分解成左连续区间当前元素右连续区间这很明显是符合逻辑的。那么把解拆分成这个形式那么就去尝试迭代这个公式。 迭代过程中连续数组的长度是从1开始递增的且每次迭代都会更新一段数组的左右端点比如 1 2 3 4 6 7 8遍历到5那么Hash[5]413,Hash[1]8,Hash[8]8;
class Solution
{
public:int longestConsecutive(vectorint nums){unordered_mapint , intHash;int res 0;for(int i 0; i nums.size(); i) {int now nums[i];if(!Hash[now]) {int left Hash[now - 1] , right Hash[now 1];int len left right 1;res max(res , len);Hash[now] len;Hash[now - left] len , Hash[now right] len;}}return res;}
};
