128.Longest-Consecutive-Sequence

128. Longest Consecutive Sequence

题目地址

https://www.lintcode.com/problem/longest-consecutive-sequence

https://leetcode.com/problems/longest-consecutive-sequence/

题目描述

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.

代码

Approach #1 One Pass

public class Solution {
    public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;
    Arrays.sort(nums);

    int longestStreak = 1;
    int currentStreak = 1;

    for (int i = 1; i < nums.length; i++) {
      if (nums[i] != nums[i - 1]) {
        if (nums[i] == nums[i - 1] + 1){
          currentStreak += 1;
        } else {
          longestStreak = Math.max(longestStreak, currentStreak);
          currentStreak = 1;
        }
      }
    }
    return Math.max(longestStreak, currentStreak);
  }
}

Approah 2: HashSet and Intelligent Sequence Building

public class Solution {
  public int longestCOnsecutive(int[] nums) {
    Set<Integer> numSet = new HashSet<Integer>();
    for (int num : nums) {
      numSet.add(num);
    }

    int longestStreak = 0;

    for (int num : numSet) {
      if (!numSet.contains(num - 1)) {
        int currentNum = num;
        int currentStreak = 1;
        while (numSet.contains(currentNum + 1)) {
          currentNum += 1;
          currentStreak += 1;
        }

        longestStreak = Math.max(longestStreak, currentStreak);
      }
    }

    return longestSteak;
  }
}