76.Longest Consecutive Sequence（最长的连续序列）

Level：

Hard

题目描述：

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

思路分析：

设置一个hashset，保存数组中出现的值，然后遍历hashset，每访问到一个值num，我们查看num-1，和num+1是否在集合中，如果存在那我们可以继续查找num-2，和num+2是否存在，我们按照这种方法查找，直到要查找的数不存在，可以计算出一个连续的序列长度，对集合中每个元素进行上述操作，最后得出一个最长的连续序列。

代码：

public class Solution{

    public int longestConsecutive(int []nums){

        if(nums==null||nums.length==0)

            return 0;

        HashSet<Integer>set=new HashSet<>();

        int res=0; //记录结果

        for(int n:nums)

            set.add(n);

        while(!set.isEmpty()){

            int num=getfirst(set);

            set.remove(num);

            int left=0;//记录当前num向左能延伸的距离

            while(set.contains(num-1)){

                left++;

                set.remove(num-1);

                num--;

            }

            int right=0; //记录当前num向右能延伸的距离

            num=num+left;

            while(set.contains(num+1)){

                right++;

                set.remove(num+1);

                num++;

            }

            res=Math.max(res,left+right+1);

        }

        return res;

    }

    public int getfirst(HashSet<Integer>set){//返回集合中第一个元素

        for(int num:set)

            return num;

        return 0;

    }

}

巴特西

76.Longest Consecutive Sequence（最长的连续序列）

Level：

题目描述：

思路分析：

代码：

最新文章

热门文章