Longest Consecutive Sequence, Leetcode 解题笔记

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

因为要求O(n)的复杂度,所以一般的sort思路都被排除了。此时应该反应出要利用hash了,因为hash的查找的复杂度是O(1)。
先把所有数字放入一个Hashset,遍历这些数字,对于每个数字,查找与他相临的左右两边的数字,找到可延伸的最长的距离就是题目要求的结果。

public class Solution {
    public int longestConsecutive(int[] num) {
        int max = 0;
        Set<Integer> set = new HashSet<Integer>();
        for(int i: num){
            set.add(i);
        }
        
        for(int i: num){
            int left = i-1;
            int right = i+1;
            int count = 1;
            while(set.contains(left)){
                count++;
                set.remove(left);
                left--;
            }
            while(set.contains(right)){
                count++;
                set.remove(right);
                right++;
            }
            max = Math.max(max, count);
        }
        return max;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s