[Leetcode][128] Longest Consecutive Sequence

문제 : leetcode.com/problems/longest-consecutive-sequence/

---

정렬되지 않은 nums 배열이 주어질 때 요소들 중 가장 긴 연속 요소들(ex, 1 2 3 4)의 길이를 구하라.

---

Union find 로 풀었다.

nums 배열을 앞에서부터 탐색하면서 탐색중인 숫자를 num이라 할 때, num-1, num+1이 나타난적 있는지 확인한다.

만일 num-1이 이전에 나왔던 숫자라면 num-1와 num의 연속적인 수 중 가장 작은 수들을 가져온다. 이는 부모배열에 저장되어야 한다.(find로 찾는다.)

찾은 부모노드가 다르다면 뒤에 있는 부모노드(num의 부모)를 앞에 있는 부모노드(num-1의 부모)로 갱신하고 연속적인 수들의 최대 길이를 갱신한다.. (union 함수)

다음으로 num+1이 이전에 나왔던 숫자라면 앞에서한 것과 마찬가지로 union 함수로 num, num+1의 부모를 하나로 합쳐주고 최대 길이를갱신한다.

 

연속적인 수들의 최대 길이들 중 최대값이 정답이된다.

 

Union-find에서 find 함수의 구현을 O(N), O(logN)에서 -> O(1)로 할 수 있으므로 총 시간복잡도는 O(N).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/128.%20Longest%20Consecutive%20Sequence.cpp