leetcode 128. Longest Consecutive Sequence ----- java

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.

就是判断数组中最长的连续数字的长度。

1、直接用排序。。当然不行了，时间复杂度超过了O(n)，虽然AC了。

public class Solution {

    public int longestConsecutive(int[] nums) {

        int result = 1;

        if( nums.length == 0)

            return result;

        Arrays.sort(nums);

        for( int i = 1;i<nums.length;i++){

            int a = 1;

            while( i<nums.length && (nums[i] == nums[i-1]+1 || nums[i] == nums[i-1]) ){

                if( nums[i] == nums[i-1]+1 )

                    a++;

                i++;

            }

            result = Math.max(a,result);

        }

        return result;

    }

}

2、用set集合。遍历两次，得出结果，由于add，remove，contains都是O(1)的复杂度，所以时间复杂度符合题意。

public class Solution {

    public int longestConsecutive(int[] nums) {

        if( nums.length == 0)

            return 0;

        Set set = new HashSet<Integer>();

        for( int num : nums)

            set.add(num);

        int result = 1;

        for( int e : nums){

            int left = e-1;

            int right = e+1;

            int count = 1;

            while( set.contains(left )){

                set.remove(left);

                count++;

                left--;

            }

            while( set.contains(right) ){

                set.remove(right);

                count++;

                right++;

            }

            result = Math.max(result,count);

        }

    return result;

    }

}

巴特西

leetcode 128. Longest Consecutive Sequence ----- java

最新文章

热门文章