128. Longest Consecutive Sequence (LeetCode, C++)

reference url : youtu.be/_KEp7pwhXAc

 

 

배경지식 : Cpp Set 자료구조

www.cplusplus.com/reference/set/set/

 

요약하면 set은

중복없이 자동정렬해주는 균형이진트리(red-black tree)이다.

 

모든 데이터를 set에 넣어주고

제약조건인 O(N) 탐색을 위해, 확인할때마다 erase 해주면서 최댓값을 구한다.

 

코드 : 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        std::set<int> set;
        int max = 0;
        for (int n: nums)
            set.insert(n);
        
        for (std::set<int>::iterator it = set.begin(); it!=set.end(); it++)
        {
            int val = *it;
            int val_end = val;
            int count;
            while(set.find(++val_end) != set.end()){
                set.erase(val_end);
            }
            while(set.find(--val) != set.end()){
                set.erase(val);
            }
            count = val_end - val - 1;
            max = max < count ? count : max;
        }
        return max;
    }
};