【LeetCode】Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest

consecutive elements sequence.

For example,

Given <code>[100, 4, 200, 1, 3, 2]</code>,

The

longest consecutive elements sequence is <code>[1, 2, 3, 4]</code>. Return

its length: <code>4</code>.

Your algorithm should run in O(n) complexity.

我首先先到的是用map（key,pre）記錄每個節點的前驅節點，然後用這個map來像樹的層序周遊一樣得到樹的最大深度

一直逾時，題目要求的是O(n)一直逾時

後面想到用空間換時間，用java的bitset類型，但是當處理[2011444,145555,5,1111111]的時候明顯會逾時，bieset

可以用來處理比較密集的資料，但是不适合用來處理比較離散的資料

經過觀察可以發現，4和3 2 1 的最大連續長度是一樣的，是以在找到其中任何一個數的最大連續序列後，可以在map中将這些序列所包含的

數全部删除，以避免重複編列。

時間複雜度為O(n) + O(n) + O(序列長度總和) 近似可以認為是O(n)