方法一：暴力遍历（可优化）

思路

题目要求找出无序数组arr中的所有连续的数字，并得出最长的连续序列的长度，最为简单的方法就是暴力遍历整个数组，找出其中最长的连续序列。

具体步骤

  • 首先数组是无序的，为了遍历查找方便需要首先将数组按照升序排序；

  • 接着是一个双重循环，第一重循环是找到连续序列的初始值i；而第二重循环则是找到以i为头的连续序列的长度；

  • 取所有连续序列的长度的最大值作为返回结果。

  • 代码如下：

    import java.util.*;
public class Solution {
/**
 * max increasing subsequence
 * @param arr int整型一维数组 the array
 * @return int整型
 */
public int MLS (int[] arr) {
    // write code here
    if (arr.length == 0){
        return 0;
    }
    // 排序
    Arrays.sort(arr);
    // 判断数组
    boolean[] flags = new boolean[arr.length];
    int index = 0;
    int res = 0;
    while(index<arr.length){
        int temp = 0;
        int curNum = arr[index];
        for(int i = index+1;i<arr.length;++i){
            // 连续，加一
            if (arr[i] == curNum+1){
                ++temp;
                curNum = arr[i];
            }
        }
        temp++;
        res = res>temp?res:temp;
        ++index;
    }
    return res;
}
}

  • 时间复杂度为：首先降序排序的时间复杂度已经到了，双重循环也需要；若是进行优化的话，最优可以达到的时间复杂度。

  • 空间复杂度为：常数级空间复杂度。

方法二：并查集

思路

由于题目被分类至并查集下，所以这里介绍一下并查集解题的方法。

具体步骤

  • 首先在需要构建一个并查集内部类，由于所给的数组，其取值范围过大，没办法以数组表示森林，所以我这里使用的是Map来表示一个森林；
  • 使用Set对arr数组中的数字去重，同时便于后面union时，判断参数是否合法；
  • 遍历数组进行union操作。
  • 具体运行过程参考下图：

  • 代码如下： 
import java.util.*;
public class Solution {

    // 用于去重，以及判断待连接的两个值是否都在所给的集合中
    Set<Integer> check = new HashSet<Integer>();

    class UF{
        // 记录连通树的最大重量，即连续序列的最大长度
        private int max = 1;
        // 使用map存储森林
        private Map<Integer,Integer> parent = new HashMap<>();
        // 记录每一课树的长度
        private Map<Integer,Integer> length = new HashMap<>();
        // 并查集内部类
        public UF(int[] nums){
             init(nums);
        }
        private void init(int[] nums){
            for(Integer i:nums){
                 // 初始化，每一个树都只有一个节点
                 parent.put(i,i);
                 length.put(i,1);
             }
        }
        public void union(int p,int q){
            // 若集合中没有对应的值，则直接返回
            if (!check.contains(p) || !check.contains(q))
                return;
            int rootP = find(p);
            int rootQ = find(q);
            // 若根节点相同，则直接返回
            if (rootP == rootQ){
                return;
            }
            // 将小树接至大树下，以尽量使树保持平衡
            if (length.get(rootP) > length.get(rootQ)){
                parent.put(rootQ,rootP);
                length.put(rootP,length.get(rootP) +
                        length.get(rootQ));
                max = Math.max(max,length.get(rootP));
            }else{
                parent.put(rootP, rootQ);
                length.put(rootQ, length.get(rootP) + length.get(rootQ));
                max = Math.max(max, length.get(rootQ));
            }
        }
        private int find(int x){
            while(parent.get(x) != x){
                int temp = parent.get(x);
                // 路径压缩
                parent.put(x,parent.get(temp));
                x = temp;
            }
            return x;
        }
        // 返回最大值
        public int getMax(){
            return max;
        }
    }
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        if(arr.length == 0){
             return 0;
        }
        UF uf = new UF(arr);
        for(int i = 0; i < arr.length; ++i)
        { 
            check.add(arr[i]); 
        }
        for(int i = 0; i < arr.length; ++i)
        { 
            // 这里是将arr[i]和其减一的值合并 
            uf.union(arr[i], arr[i] - 1); 
        } 
        return uf.getMax(); 
} 
}

时间复杂度：，并查集操作的时间消耗主要在find方法处，这里采用路径压缩，可以使得时间复杂度降为，而遍历需要，所以时间复杂度为；

空间复杂度：，需要集合进行辅助运行，空间复杂度为数据量即n。