128. Longest Consecutive Sequence
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/longest-consecutive-sequence/
内容描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
思路1 **- 时间复杂度: O(n)*- 空间复杂度: O(1)***
先对数组进行排序。在用unique()函数去除重复的数字。在遍历数组，找到最长的连续数字。时间复杂度为O(nlgn)。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(!nums.size())
return 0;
sort(nums.begin(),nums.end());
auto end_pos = unique(nums.begin(),nums.end());
int j = end_pos - nums.begin();
int ans = 1,sum = 1;
for(int i = 1;i < j;++i)
{
if(nums[i] == nums[i - 1] + 1)
sum++;
else
sum = 1;
ans = max(ans,sum);
}
return ans;
}
};
思路2 **- 时间复杂度: O(nlgn)*- 空间复杂度: O(1)*** c++中的unordered_map是用hash桶实现的，所以可以在线性时间内完成。县遍历数组，用nums[i]作为unordered_map的键值。0作为 value。0表示此时的nums[i]还没被遍历过。接着遍历数组，用DFS搜索每个nums[i]的最长连续数字。被遍历过的nums[i]的unordered_map值设为1
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(!nums.size())
return 0;
unordered_map<int,int> m;
for(int i = 0;i < nums.size();++i)
m[nums[i]] = 0;
int ans = 0;
for(int i = 0;i < nums.size();++i)
{
if(m[nums[i]])
continue;
m[nums[i]] = 1;
int temp = nums[i] + 1,sum = 0;
while(m.find(temp) != m.end())
m[temp++] = 1;
sum = temp - nums[i];
temp = nums[i] - 1;
//cout << temp << endl;
while(m.find(temp) != m.end())
m[temp--] = 1;
sum += (nums[i] - temp - 1);
ans = max(ans,sum);
}
return ans;
}
};
