LeetCode Q128: Longest Consecutive Sequence (hard)

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution:

Because requiring only take O(n), so considering using Hash table. For each number, search backward and forward.

	class Solution {
	public:
	int longestConsecutive(vector<int>& nums) {
	int len=0;
	if(nums.empty())
	return len;
	unordered_map<int, int> myMap;
	for(int i=0; i<nums.size(); i++){
	myMap[nums[i]]=1;
	}
	for(int i=0; i<nums.size(); i++){
	int n=nums[i];
	if(myMap[n]==1){
	int tmp1=n-1;
	while(myMap[tmp1]==1){
	myMap[tmp1]=0;
	tmp1--;
	}
	tmp1++;
	int tmp2=n+1;
	while(myMap[tmp2]==1){
	myMap[tmp2]=0;
	tmp2++;
	}
	tmp2--;
	myMap[n]=0;
	int tmpLen=tmp2-tmp1+1;
	len=tmpLen>len? tmpLen:len;
	}
	else
	continue;
	}
	return len;
	}
	};

view raw Q128LongestConsecutiveSequence.cpp hosted with ❤ by GitHub