leetcode----128.最长连续序列

128.最长连续序列（并查集）

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

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

思路：首先想到的是先排序，然后直接找最长连续序列，但是这样时间复杂度达不到要求

• 哈希表

• 对于数组中的每一个数num，假设以num为起点，寻找最长连续序列，需要遍历整个数组寻找是否存在num+1，num+2...num+y。则以num为起点的最长连续子序列长度为y+1。不断枚举数组中的每一个元素，最终得到最长连续序列的长度。

• 对于匹配的过程，暴力的方法是O(n)遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1)的时间复杂度。

• 我们发现外层循环，也就是寻找以数组中每个数为起点的最长连续子序列的过程中，存在一些重复步骤，例如以num为例，假设存在num+1，num+2...num+y。那么以这些数为起点的最长连续序列长度肯定小于以num为起点的，所以在外层循环遍历到这些数的时候可以跳过，以优化时间复杂度。接下来的重点就是如何判断哪些数需要跳过？

• 假设以num为起点的序列为最长连续序列，那么数组中肯定不存在num的前驱节点num-1。若存在的话，则以当前数为起点的序列肯定不是最长连续序列。因此我们每次在哈希表中检查是否存在 num-1即能判断是否需要跳过了。

• 然后分析时间复杂度，这个思路虽然有两层循环，但是数组中的每个数只会进入内层循环一次(只有当一个数为连续序列的第一个数时，才会进入内层循环寻找其后面连续的数)。外层循环的时间复杂度为O(n)。所以这个思路的时间复杂度为O(n)。

class Solution {
    public int longestConsecutive(int[] nums) {
       if(nums.length == 0 || nums.length == 1) return nums.length;
       Set<Integer> set = new HashSet();
       for(int num: nums){
           set.add(num);
       }

       int maxLen = 0;
       for(int num: nums){
           if(!set.contains(num - 1)){
               int curNum = num;
               int curLen = 1;
               while(set.contains(curNum + 1)){
                   curNum += 1;
                   curLen += 1;
               }
               maxLen = Math.max(maxLen, curLen);
           }
       }
       return maxLen;
    }
}

• 并查集学习
• 题解来自这里
• 数组中出现重复值直接忽略，不会造成影响
  使用并查集 ，需要结构：
  1.int[] parents,数组每个元素作为节点，parents[i]表示i这个节点的父在的位置
  2.int[] sizeMap,只有这个节点是集合的头才有效，表示这个序列的长度
  3.nodesMap<Integer,Integer> Key:数，value:所在下标
  并查集需要实现方法：
  union(Integer,Integer),将这两个数对应的集合进行合并
  思路：
  遍历数组，当前数是nums[i],让nums[i]找nums[i]-1和nums[i]+1进行集合合并
  由于处理，不会被重复值的情况给混乱，只要是存在nums[i]-1和nums[i]+1就合并就能连续了

class Solution {

    public static class UnionFind{
        int[] parents;
        int[] sizeMap;
        HashMap<Integer,Integer> nodesMap;
        int maxSeqLen = 1;//全局维护最长序列长度
        public UnionFind(int[] nums){
            int N = nums.length;
            parents = new int[N];
            sizeMap = new int[N];
            nodesMap = new HashMap<>();
            for(int i = 0;i<nums.length;i++){
                parents[i] = i;
                sizeMap[i] = 1;
                nodesMap.put(nums[i],i);
            }            
        }
        public void union(int a,int b){
            if(!nodesMap.containsKey(a)||!nodesMap.containsKey(b)){
                return;
            }
            int aFather = findFather(nodesMap.get(a));
            int bFather = findFather(nodesMap.get(b));
            if(aFather==bFather) return;
            //小挂大  按秩压缩
            int size = sizeMap[aFather] + sizeMap[bFather];
            maxSeqLen = Math.max(maxSeqLen,size);
            int min = sizeMap[aFather]<sizeMap[bFather]?aFather:bFather;
            int max = aFather==min?bFather:aFather;
            parents[min] = max;
            sizeMap[max] = size;
        }
        public int findFather(int idx){
            int parent;
            Stack<Integer> path = new Stack<>();
            while((parent=parents[idx])!=idx){
                path.push(idx);
                idx = parent;
            }
            //路径压缩
            while(!path.isEmpty()){
                parents[path.pop()] = parent;
            }
            return parent;
        }
    }
    public int longestConsecutive(int[] nums) {
        if(nums==null||nums.length<=0) return 0;
        UnionFind set = new UnionFind(nums);
        for(int num:nums){
            set.union(num-1,num);
            set.union(num+1,num);
        }
        return set.maxSeqLen;
    }
}