128. Longest Consecutive Sequence (1)

Link

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.

Solution

  public int longestConsecutive(int[] nums) {
        //針對每個值看他的後繼數是否有出現
        Set<Integer> set = new HashSet<>();
        for(int i : nums){
            set.add(i);
        }
        int maxValue = 0;
        for(int num : set){
            //避免算到之前算過的，一律從他上個數沒有的開始算, 即num為該LCS最小的
            if(!set.contains(num-1)) {
                int count = 1; //REMEMBER count最小是1
                while (set.contains(++num)) {
                    count++;
                }
                maxValue = Math.max(maxValue, count);
             }
        }
        return maxValue;
    }