Longest Consecutive Sequence -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/longest-consecutive-sequence/
這道題是要求出最長的整數連續串。我們先說說簡單直接的思路，就是先排序，然後做一次掃描，記錄當前連續串長度，如果連續串中斷，則比較是否為當前最長連續串，並且把當前串長度置0。這樣時間復雜度是很明確，就是排序的復雜度加上一次線性掃描。如果不用特殊的線性排序算法，復雜度就是O(nlogn)。
其實這個題看起來是數字處理，排序的問題，但是如果要達到好的時間復雜度，還得從圖的角度來考慮。思路是把這些數字看成圖的頂點，而邊就是他相鄰的數字，然後進行深度優先搜索。通俗一點說就是先把數字放到一個集合中，拿到一個數字，就往其兩邊搜索，得到包含這個數字的最長串，並且把用過的數字從集合中移除（因為連續的關系，一個數字不會出現在兩個串中）。最後比較當前串是不是比當前最大串要長，是則更新。如此繼續直到集合為空。如果我們用HashSet來存儲數字，則可以認為訪問時間是常量的，那麼算法需要一次掃描來建立集合，第二次掃描來找出最長串，所以復雜度是O(2*n)=O(n)，空間復雜度是集合的大小，即O(n)。代碼如下：

public int longestConsecutive(int[] num) {
    if(num == null || num.length == 0)
        return 0;
    HashSet set = new HashSet();
    int res = 1;
    for(int i=0;ires)
            res = len;
    }
    return res;
}