[LeetCode] 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.

 

Approach

배열이 sorting되어있으면 아주 쉽다.

priority queue를 활용한 heap에 배열을 옮겨 담고

하나씩 빼면서 연속인지 아닌지 확인하면 됨

하지만 이 방법은 시간복잡도가 O(nlogn)이다

 

Optimize

sorting을 안하고 unordered_set을 사용하면 O(n)만에 풀 수 있다.

배열을 unordered_set에 옮겨닮고

하나씩 꺼내면서 +1, -1한 값들이 set안에 들어있는지 확인한다. (확인 후 set에서 삭제)

이런 식으로 최대 연속된 길이를 측정하면 된다.

 

Code

priority queue: https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestConsecutiveSequence.cpp

chi3236/algorithm

set: https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestConsecutiveSequence_O(n).cpp

불러오는 중입니다...