因此開始記錄依照不同資料結構搭配Leetcode來練習
方便未來可以隨時拿來複習
Leetcode出處 : https://leetcode.com/problems/longest-consecutive-sequence/
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.
分析
因為題目說是unsorted integer,但是又說complexity必須是O(n)
因此,需要想到用hash table
我打算用unsorted_set來解此問題,並且以set裡面的元素為中心向外尋找下一個職是否在set裡,直到不連續為止
乍看之下時間複雜度是O(n^2),但是因為在numsSet.erase(j)後,之前出現過的就不會再進入內層兩個迴圈裡,因此類積下來的次數就是nums元素個數。
另外,如果沒有說到要O(n),我們可以先排序再做,因此時間複雜度就是O(n log n)
Sample Code (C++)