Longest Consecutive Sequence

出处

最长连续序列

Get the length of the longest consecutive elements sequence in an array. For example, given [31, 6, 32, 1, 3, 2],the longest consecutive elements sequence is [1, 2, 3]. Return its length: 3.

Solution

如何判断当前节点i是否属于一个序列?如果array[i] – 1存在在数组中,那么array[i]就可以作为后继加入序列。类似地,如果array[i] + 1存在在数组中,那么array[i]就可以作为前驱加入序列。我们发现处理当前节点需要依赖于之前的部分结果:判断array[i] – 1,array[i] + 1是否存在于数组中。如何保存之前的处理结果?可以使用哈希表。很显然,键对应于数值。但对于这个问题,value并不是那么明显,需要进一步分析。

一般而言,键用于快速判断哈希表中有没有我们需要的元素,值提供我们需要的结果。在这题中,我们期望于获得怎样的部分解呢?我们需要知道现在已经构成的序列是怎样的。由于序列是一系列连续整数,所以只要序列的最小值以及最大值,就能唯一确定序列。“而所谓的“作为后继加入序列”,“作为前驱加入序列”,无非就是更新最大最小值。所以哈希表的值可以是一个记录最大/最小值的结构,用以描述当前节点参与构成的最长序列。

Complexity

根据上述算法,我们只要扫描一遍整个数组就能获得结果,时间复杂度O(n),附加空间O(n)。

Code

class Bound{
    int high;
    int low;
    public Bound(int h, int l){
        high = h;
        low = l;
    }
}

int lcs(int[] arr){
    HashMap<Integer, Bound> range = new HashMap<Integer, Bound>();
    int maxLen = 0;
    for (int i = 0; i < arr.length; i++){
        if (!range.containsKey(arr[i]){
            int local = arr[i];
            int high = local;
            int low = local;
            
            if (range.containsKey(local-1){
                low = range.get(local-1).low;
            }
            
            if (range.containsKey(local+1){
                high = range.get(local+1).high;
            }
            
            if (high - low + 1 > maxLen){
                maxLen = high - low + 1;
            }
            
            range.put(local, new Bound(high, low)):
        } else {
            continue;
        }
    }
    return maxLen;
}