128. 最长连续序列
乍一看感觉很简单，一看要用O(n)???
因为我觉得题目很难而且题目看起来很简单，感觉以后会用到，做个记录
1.朴素做法
- 思路
答:任何一段连续的数都有一个左端点：比如（1，2，3，4）的左端点是1，且找到1之后，发现（1，2，3，4）为最长的连续区间，那么从2，3，4为左端点的区间都不需要继续尝试了，因为他们都比1为左端点的区间短。
那么我们只需要找所有的左端点，然后不停比较更新即可。- 怎么找左端点？只要没有比它更小的数，那么就是左端点：比如[100,1,3,2,4],这个数组有两个左端点：100，1。
- 用哈希表空间换时间，这样就不需要每次找到一个数，然后去for循环判断有没有比他小的数以及他后面接着几个连续的数
class Solution
{
public:
int longestConsecutive(vectorint&服务器托管网gt;& nums)
{
int n=nums.size();
unordered_setint>Hash; //set只有一个参数，然后去重，重复的键值不会被插入
for(int i=0;in;i++)
Hash.insert(nums[i]);
int ans=0;
for(int i=0;in;i++)
{
if(Hash.find(nums[i]-1)!=Hash.end())//num[i]-1存在，nums[i]不是左端点
continue;
else
{
int x=nums[i]+1; //nums[i]是左端点，从x开始尝试找
int len=1;
while(Hash.find(x)!=Hash.end())
{
x++;
len++;
}
ans=max(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];
}
else服务器托管网
return x;
//return a.count(x)?a[x]=find(a[x]):x;
}
int longestConsecutive(vectorint>& nums)
{
for(auto i:nums) //这一步很巧妙，这个错位的赋值使find函数一步到位，只要使连续的，那么就把所有连续的数都放在集合里了。
a[i]=i+1;
int ans=0;
for(auto i:nums)
{
int y=find(i+1);
ans=max(ans,y-i);
}
return ans;
}
};
3.动态规划
- 思路：
最终求的是最长的连续数组，那么可以把解分解成：左连续区间+当前元素+右连续区间，这很明显是符合逻辑的。那么把解拆分成这个形式，那么就去尝试迭代这个公式。- 迭代过程中，连续数组的长度是从1开始递增的，且每次迭代都会更新一段数组的左右端点，比如： 1 2 3 4 6 7 8，遍历到5，那么Hash[5]=4+1+3,Hash[1]=8,Hash[8]=8;
class Solution
{
public:
int longestConsecutive(vectorint>& nums)
{
unordered_mapint , int>Hash;
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;
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: keycloak~网站对接到Keycloak的步骤
新网站对接到KC的部署 kc的环境 向kc申请自己的客户端 kc的登录接口 通过code换token接口 刷新token接口 kc的用户信息接口 kc的jwt token说明 1. kc的环境 测试环境：https://test-kc.xxx.com 预发布环…
