128. Longest Consecutive Sequence

三刷 06/2022

Version #1 HashSet

还是完全没有思路，看了答案才写出来

Time O(N)

Space O(N)

Runtime: 38 ms, faster than 78.17% of Java online submissions for Longest Consecutive Sequence.

Memory Usage: 74.5 MB, less than 58.96% of Java online submissions for Longest Consecutive Sequence.

class Solution {

    public int longestConsecutive(int[] nums) {

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

        for (int num : nums) {

            set.add(num);

        }

        int max = 0;

        for (int num : nums) {

            if (!set.contains(num)) {

                continue;

            }

            // Thie is not the start number of a sequence

            int start = num, end = num;

            while (set.remove(start - 1)) {

                start--;

            }

            while (set.remove(end + 1)) {

                end++;

            }

            max = Math.max(max, end - start + 1);

        }

        return max;

    }

}

二刷
Version #4 Union Find Index
另外一个完全不同的思路是对index进行Union Find
感觉比我写的要好
Ref
https://leetcode.com/problems/longest-consecutive-sequence/discuss/41062/My-Java-Solution-using-UnionFound

Version #3 Union Find 2 HashMap
这道题的精华是说union find不一定用array表示
只有当key是 0 -> N - 1的时候 size[] id[]才适用
其他情况下可以用hashmap代替

13.12 %
class Solution {
    class UF {
        // key -> num, value -> size
        private Map<Integer, Integer> size;
        // key -> num, value -> parent
        public Map<Integer, Integer> id;
        public int maxSize;
        public UF(int[] nums) {
            size = new HashMap<>();
            id = new HashMap<>();
            for (int num : nums) {
                size.put(num, 1);
                id.put(num, num);
            }
            maxSize = 1;
        }
   
        private int root(int i) {
            while (id.get(i) != i) {
                int parent = id.get(i);
                id.put(i, id.get(parent));
                i = id.get(parent);
            }
            return i;
        }
   
        public void union(int p, int q) {
            int rootP = root(p);
            int rootQ = root(q);
            if (rootP == rootQ) {
                return;
            }
            if (size.get(rootP) < size.get(rootQ)) {
                id.put(rootP, rootQ);
                size.put(rootQ, size.get(rootP) + size.get(rootQ));
                maxSize = Math.max(maxSize, size.get(rootQ));
            } else {
                id.put(rootQ, rootP);
                size.put(rootP, size.get(rootP) + size.get(rootQ));
                maxSize = Math.max(maxSize, size.get(rootP));
            }
        }
    }

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        UF uf = new UF(nums);
        for (int num : nums) {
            if (uf.id.keySet().contains(num + 1)) {
                uf.union(num, num + 1);
            }
            if (uf.id.keySet().contains(num - 1)) {
                uf.union(num, num - 1);
            }
        }
        return uf.maxSize;
    }
}



Version #2 HashSet
三刷
这个题的问题在于如果新来的num，它的num - 1,num + 1都有值的话
此时的num就不是一个边界
但是也要塞到hashmap里面因为如果6 来了 给你更新了5和7的长度为3
但是没有塞到hashmap里面
那么如果再来一个6，就会造成5和7的长度变成了7
所以这里把6塞进去相当于一个visited的作用，具体的value无所谓


16.88 %
class Solution {
    public int longestConsecutive(int[] nums) {
        // the length of sequence starts/ends with key
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int num : nums) {
            if (map.containsKey(num)) {
                continue;
            }
            int left = map.getOrDefault(num - 1, 0);
            int right = map.getOrDefault(num + 1, 0);
            int sum = left + right + 1;
            max = Math.max(max, sum);
            // if (left == 0 || right == 0) {
            //     map.put(num, sum);
            // } else {
            //     map.put(num, 1);
            // }
            map.put(num, sum);
            map.put(num - left, sum);
            map.put(num + right, sum);
        }
        return max;
    }
}


一开始看了半天完全不会做
找了个hashset的答案，就是iterate整个array当确定当前值是某序列的第一个时，向后扫
然后扫到不能扫了，更新max
看了一刷的hashmap答案，感觉更好，就是给随便一个数就往前往后扫，扫到不能扫了 更新max right - left + 1
这两种方法都是一边检查一遍从set/map里面remove
74.81 %
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i]) && !set.contains(nums[i] - 1)) {
                int count = 0;
                int num = nums[i];
                while (set.contains(num)) {
                    set.remove(num);
                    num++;
                    count++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}

一刷
Version #1 HashMap(Better than hashset)
Initialize a hashset and add every number into it.
Iterate through the number array.
For every current number, look for its 2 neighbors in the hashset.
Keep expanding the current consecutive sequence and remove every visited node.
Update the max length.
 71.13%

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        int left = 0;
        int right = 0;
        for (int n : nums) set.add(n);
        int longest = 0;
        for (int n : nums) {
            if (set.contains(n)) {
                int down = n;
                while (set.contains(down - 1)) {
                    set.remove(down - 1);
                    down--;
                }
                int up = n;
                while (set.contains(up + 1)) {
                    set.remove(up + 1);
                    up++;
                }
                longest = Math.max(longest, up - down + 1);
            }
        }
        return longest;
    }
}