Longest Consecutive Sequence

Med Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity.

Thoughts

看到longest seq 想到了DP。f[i]设为以i为尾的最长连续子序列的长度。由于没有排序，我们需要一种数据结构能O(1)时间查询之前访问过的元素中有没有是nums[i]前辈的，也就是hash set了。这时发现其实只要稍微操作一下set而不用真的使用DP. 先把所有元素放入set中，然后重新遍历nums,然后依次删除nums[i]的前后相连所有元素并计数即可。

Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] nums) {
        Set<Integer> visited = new HashSet<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            visited.add(nums[i]);
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = nums[i], count = 1;
            int previous = num - 1, next = num + 1;
            while (!visited.isEmpty() && visited.contains(previous)) {
                visited.remove(previous);
                previous--;
                count++;
            }
            while (!visited.isEmpty() && visited.contains(next)) {
                visited.remove(next);
                next++;
                count++;
            }
            max = Math.max(max, count);
        }

        return max;
    }    
}

Analysis

每个元素出入set一次，总耗时O(n), 空间O(n).