LeetCode220814-20_84、最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-consecutive-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解一、使用HashSet存储元素，去重，然后找连续数中最小的元素，若存在后续数值进行长度的累加。

class Solution{
    public int longestConsecutive(int[] nums){
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        int res = 0;
        //从HashSet用for循环遍历取值！！！去重！！！
        for(int num : set){
            if(!set.contains(num - 1)){
                int cur = num;
                int len = 1;
                while(set.contains(cur + 1)){
                    cur++;
                    len++;
                }
                res = Math.max(res, len);
            }
        }
        return res;
    }
}

题解二、使用HashSet，直接以自身为起始点，存在连续数值时不断对元素值进行累加，最终用插值表示最长连续距离。

class Solution{
    public int longestConsecutive(int[] nums){
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        int res = 0;
        for(int num : set){
            if(!set.contains(num - 1)){
                int cur = num;
                while(set.contains(cur + 1)){
                    cur++;
                }
                res = Math.max(res, cur - num + 1);
            }
        }
        return res;
    }
}

题解三、使用HashMap存储数值对应的右边界，进行更新，和题解二一致，进行边界与起始值的差值求取最长距离。

class Solution{
    public int longestConsecutive(int[] nums){
        Map map = new HashMap<>();
        for(int num : nums){
            map.put(num, num);
        }
        int res = 0;
        for(int num : nums){
            if(!map.containsKey(num - 1)){
                int right = map.get(num);
                while(map.containsKey(right + 1)){
                    right++;
                }
                //更新右边界，防止连续序列的最左元素重复时再次进入while，进行遍历求right
                map.put(num, right);
                res = Math.max(res, right - num + 1);
            }
        }
        return res;
    }
}

题解四、动态规划，HashMap存储元素和他的最长连续距离，首次经过的元素才可进行求取，保证去重。只更新(num - left) 和(num + right)原因是，在中间的值已经在 (num - 1) 和 （num + 1）的key值条件下取过值了，不可能再用到。

class Solution{
    public int longestConsecutive(int[] nums){
        Map map = new HashMap();
        int res = 0;
        for(int num : nums){
            if(!map.containsKey(num)){
                //每个元素最多最为一次左右元素被提及。
                //一次当作左边界被取到，下次在使用元素时，只能是作为右边界，因为上方的if条件
                int left = map.getOrDefault(num - 1, 0);
                int right = map.getOrDefault(num + 1, 0);
 
                int cur = left + right + 1;
                res = Math.max(res, cur);
                //将num添加入map，标记为已访问，和if条件呼应，若不标记，当左右left，right均可从map取到，不为0时，这个元素一直不被添加进map，会出现边界错误问题。
                map.put(num, 1);
                //更新左右边界，为下次用到左右边界数值时做准备。
                map.put(num - left, cur);
                map.put(num + right, cur);
            }
        }
        return res;
    }
}

题解五、并查集，size求取最长连续序列

①创建parent[]数组，作为相连根节点

②创建size[]数组，作为相连序列长度

③union合并时，相同根节点跳过（本题无相同根节点情况，因为都是只允许单次访问，并且进行根节点变换），不相同根节点，合并根节点的同时（新的指向已经存在的可降低树高），size求和

④find，压缩路径，递归找到根节点。

⑤求取最大size

class Solution{
    public int longestConsecutive(int[] nums){
        Map map = new HashMap<>();
        UF uf = new UF(nums.length);
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])) continue;
            if(map.containsKey(nums[i] - 1)){
                uf.union(i, map.get(nums[i] - 1));
            }
            if(map.containsKey(nums[i] + 1)){
                uf.union(i, map.get(nums[i] + 1));
            }
            map.put(nums[i], i);
        }
        return uf.getMaxSize();
    }
}
 
class UF{
    private int[] parent;
    private int[] size;
 
    public UF(int n){
        parent = new int[n];
        size = new int[n];
        Arrays.fill(size, 1);
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }        
    }
 
    public void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ) return;
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
 
    public int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }   
    
    public int getMaxSize(){
        int res = 0;
        for(int i = 0; i < parent.length; i++){
            if(parent[i] == i){
                res = Math.max(res, size[i]);
            }
        }
        return res;
    } 
 
}