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.class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.size()==0) return 0;
map<int,int> mp;
for(int i=0;i<nums.size();++i)
{
mp[nums[i]]++;
}
int cnt=1,ans=1;
vector<int> v;
for(auto p=mp.begin();p!=mp.end();++p)
{
v.push_back(p->first);
}
for(int i=0;i<v.size()-1;++i)
{
if(v[i]+1==(v[i+1]))
{
++cnt;
}else{
ans=max(ans,cnt);
cnt=1;
}
}
ans=max(ans,cnt);
return ans;
}
};
--------------------------------------------------------------------------------------------------------------------------
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num-1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum+1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
-----------------------------------------------------------------------------------------------------------------------
class Solution:
def longestConsecutive(self, nums):
longest_streak = 0
num_set = set(nums)
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
