leetcode练习题 longest-consecutive-sequence

解题思路

本题提供两种思路：
1、对数组进行排序并删除重复元素，之后遍历一遍数组并保存包含当前元素的最大连续序列，但是涉及到sort排序，时间复杂度为O(nlogn)，不过还是能通过。
2、第二种方法是之后看了讨论区得到的方法，用一个set存下数组中的所有元素，因为set会除去重复元素，之后遍历数组元素，并不断往左右扩展，即在set中查看是否能找到顺序递减和顺序递增的元素并删除，记录当前的最大连续序列。其中，删除元素是不会影响之后的结果，因为能顺序扩展到的元素已经扩展到了，不能继续扩展了才停止的，之后的元素按同样的方式求各自的最大连续序列，并与已有的最大长度进行比较，取最大值。

解题代码

1、

#include<algorithm>
class Solution {
public:int longestConsecutive(vector<int> &num) {if(num.size() == 1)return 1;sort(num.begin(),num.end());vector<int>::iterator ite = unique(num.begin(),num.end());num.erase(ite,num.end());int *dp = new int[num.size()];for(int i = 0;i < num.size();i++)dp[i] = 1;int res = 1;for(int i = 1;i < num.size();i++){if(num[i] == num[i - 1] + 1)dp[i] = dp[i - 1] + 1;res = res > dp[i] ? res : dp[i];}return res;}
};

2

#include<set>
class Solution {
public:int longestConsecutive(vector<int> &num) {set<int>s(num.begin(),num.end());int res = 1;for(int i = 0;i < num.size();i++){int tmp = num[i];if(s.find(tmp) == s.end())continue;int l = tmp - 1,r = tmp + 1;while(s.find(l) != s.end())s.erase(l--);while(s.find(r) != s.end())s.erase(r++);res = res > (r - l - 1) ? res : (r - l - 1);}return res;}
};