128. Longest Consecutive Sequence (M)

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

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

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 105

• -109 <= nums[i] <= 109

Solution:

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

Version 1:

既然要O(n)算法，排序显然不行，所以自然想到用hash table。将序列中的所有数存到一个unordered_set中。对于序列里任意一个数A[i]，我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在，继续找A[i]+2和A[i]-2，以此类推，直到将整个连续序列找到。为了避免在扫描到A[i]-1时再次重复搜索该序列，在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时，所有连续序列搜索结束。

复杂度：由于每个数字只被插入set一次，并删除一次，所以算法是O(n)的。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        int longest = 0;
        for (int i = 0; i < nums.length; i++) {
            int down = nums[i] - 1;
            while (set.contains(down)) {
                set.remove(down);
                down--;
            }
            
            int up = nums[i] + 1;
            while (set.contains(up)) {
                set.remove(up);
                up++;
            }
            
            longest = Math.max(longest, up - down - 1);
        }
        
        return longest;
    }
}

Version 2:

• 相比标准答案，此解是one pass solution

• 用一个HashMap来记录还有数字i的连续序列的长度，该长度等于左右连续序列长度的和加 - count(i) = count(i - 1) + count(i + 1) + 1

• 需要注意的是，当加入一个数字i的时候，除了要利用上面公式更新该点的序列长度以外，还要把它左边和右边连续序列端点对应的长度改掉 举个例子：4(1)表示含有数字4的连续序列长度是1 4,5,3,1,2 => 4(1) => 4(2), 5(2) => 4(2), 5(3), 3(3) => 4(2), 5(3), 3(3), 1(1) => 4(2), 5(5), 3(3), 1(5), 2(5)

public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        if (num == null || num.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> streak = new HashMap<>();
        
        int max = 0;
        for (int n : num) {
            if (streak.containsKey(n)) {
                continue;
            }
            int leftCount = 0, rightCount = 0;
            if (streak.containsKey(n - 1)) {
                leftCount = streak.get(n - 1);    
            }
            if (streak.containsKey(n + 1)) {
                rightCount = streak.get(n + 1);
            }
            int count = leftCount + rightCount + 1;
            max = Math.max(max, count);
            streak.put(n, count);
            streak.put(n - leftCount, count);
            streak.put(n + rightCount, count);
        }
        
        return max;
    }
}

Version 3:

pq排了一下序， set去了一下重复， 剩下就没啥难度了， 应该算O(N)的吧

public class Solution {
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    public int longestConsecutive(int[] num) {
        // write your code here
        if (num == null || num.length == 0) {
            return 0;
        } 
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            if (!set.contains(num[i])) {
                set.add(num[i]);
                pq.offer(num[i]);
            }
        }
        
        int res = 1;
        int temp = 1;
        int start = pq.poll();
        while (!pq.isEmpty()) {
            int curr = pq.poll();
            if (curr == start + 1) {
                start = curr;
                temp++;
            } else {
                temp = 1;
                start = curr;
            }
            res = Math.max(res, temp);
        }
        
        return res;
    }
}