[c++] 128. Longest Consecutive Sequence

128. Longest Consecutive Sequence

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

You must write an algorithm that runs in O(n) time.

 

 한줄해석  : 배열내에서 연속적인 원소의 최대 길이를 찾아 반환하라 

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

  Idea  

100과 연속되는 수는 99와 101 이다. 따라서, 100이 입력으로 들어온다면 

1) 99, 98, 97.... 들이 배열내에 있는지 체크후 있으면 count 를 1 올린다. 

2) 101, 102, 103...들이 배열내에 있는지 체크후 있으면 count를 1 올린다. 

 

따라서 감소하는 방향, 증가하는 방향으로 나누어 해당 원소의 존재여부를 체크 할 수 있다. 

 

 Data Structure 

이 문제에서는 unordered_set 자료형을 사용할 것인데, 

이 자료형의 특징은 key와 value를 가지는 unordered_map과 달리, 배열내 해당 값의 존재 유무를 판별 할 때 사용한다. 

 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
        unordered_set<int> box;
        int maxcnt=0;
        for(auto a:nums)
            box.insert(a);
        
        while(box.size()!=0){
            int number = *box.begin();
            box.erase(number);
            int cnt=1;
            // find left
            int left=number;
            while(box.find(--left)!=box.end()){                
                cnt++;               
                box.erase(left);
            }
            
            // find right
           int right=number;
            while(box.find(++right)!=box.end()){
                cnt++;
                box.erase(right);
            }
            maxcnt  = max(cnt,maxcnt);          
            
        }
        return maxcnt;
        
        
    }
};