[Leetcode 128][Medium] 最长连续序列
目录
题目描述
整体思路
具体代码
题目描述
原题链接
整体思路
首先看到找连续升序排序的最长序列长度，想到对数组进行排序预处理。但是排序算法时间复杂度需要O(nlogn)，题目要求时间复杂度为O(n)。因此不能进行排序与处理
接着想到数据结构哈希表，哈希表适合用于无序的数据问题。因此可以将数组元素全部存入哈希表，而后遍历哈希表，每次遍历都要找出连续升序排序的序列的头。找到头就要继续找下一个元素直到序列尾。然后保留每次寻找过程的序列长度的最大值。
具体代码
class Solution {
public:int longestConsecutive(vector<int>& nums) {if(nums.size()==0) return 0;//题目中说了数组长度可能为0set<int> s;for(int i:nums) s.insert(i);int ml=INT_MIN;for(int i:s){if(!s.count(i-1)){//连续升序序列中，不可能有比序列头小1的元素int cl=1;int nxt=i+1;while(s.count(nxt)){cl++;nxt++;}ml=max(ml,cl);}}return ml;}
};