剑指offer_II_119 最长连续序列

题目

题目描述：

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

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

0 <= nums.length <= 104
-109 <= nums[i] <= 109

实现

主函数：为了测试UT

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 0, 1};
        int result = longestConsecutive(nums);
        System.out.println(result);
    }

暴力做法：时间复杂度O(n logn)

/**
     * 暴力做法
     * 耗时32ms，内存消耗57MB
     *
     * @param nums 集合
     * @return 最长序列
     */
    private static int longestConsecutive(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        // DualPivotQuicksort双轴快排，数据量小插入排序，数据量大归并排序，时间复杂度O(n log(n))
        Arrays.sort(nums);
        // 去重时间复杂度O(n)
        int[] nums_distinct = Arrays.stream(nums).distinct().toArray();
        int longestLen = 0;
        int start = 0;
        int end;
        // 遍历一遍时间复杂度O(n)
        for (end = 1; end < nums_distinct.length; end++) {
            if (nums_distinct[end] != nums_distinct[end - 1] + 1) {
                start = end;
            }
            longestLen = Math.max((end - start + 1), longestLen);
        }
        longestLen = Math.max((end - start), longestLen);
        return longestLen;
    }

哈希表遍历：时间复杂度O(n)

/**
     * 哈希表遍历
     * 耗时17ms，内存消耗56.3MB
     *
     * @param nums 集合
     * @return 最长序列
     */
    private static int longestConsecutive(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        // 直接转成HashSet，add、delete、remove、contains时间复杂度O(1)
        Set set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int longestLen = 0;
        for (Integer element : set) {
            // 即从[element, x]开始遍历到x
            if (!set.contains(element - 1)) {
                int currentElement = element;
                int currentLen = 1;
                while (set.contains(currentElement + 1)) {
                    currentElement += 1;
                    currentLen += 1;
                }
                longestLen = Math.max(longestLen, currentLen);
            }
        }
        return longestLen;
    }

哈希表+并查集：时间复杂度O(n logn)

/**
     * 图论——并查集（Union-find Set）是一种精巧的数据结构，主要用于处理一些不相交集合的合并问题
     * 一些常见的用途有求连通子图、求最小生成树的Kruskal算法和求最近公共祖先（LCA）等
     * 主要操作：
     * 1、初始化 init
     * 2、查找 find
     * 3、合并 union
     */
    static class UnionFind {
        private Map parents;
        // 有参构造函数初始化哈希表，相当于用fa[]来存储每个元素的父节点。
        UnionFind(int[] nums) {
            this.parents = new HashMap<>();
            // 初始化时父节点设置为自己
            Arrays.stream(nums).boxed().forEach(element -> parents.put(element, element));
        }
 
        // 通过哈希表查询时间复杂度O(1)
        int find(int x) {
            // 递归出口，当到达了祖先位置，就返回祖先
            if (parents.get(x) == x) {
                return x;
            }
            // find(parents.get(x))不断往上查找祖先，也进行了路径压缩
            parents.put(x, find(parents.get(x)));
            return parents.get(x);
        }
 
        // 合并，把y作为x的parents
        void union(int x, int y) {
            if (parents.containsKey(y)) {
                parents.put(x, y);
            }
        }
    }
 
    /**
     * 哈希表 + 并查集 (「单向链表」转换成了「树」)
     * 耗时47ms，内存消耗61.3MB
     * @param nums 集合
     * @return 最长序列
     */
    private static int longestConsecutive(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int longestLen = 0;
        UnionFind uf = new UnionFind(nums);
        for (int i = 0; i < nums.length; i++) {
            uf.union(nums[i], nums[i] + 1);
        }
        for (int i = 0; i < nums.length; i++) {
            longestLen = Math.max(longestLen, uf.find(nums[i]) - nums[i] + 1);
        }
        return longestLen;
    }

并查集的步骤主要有：初始化 ——>  查找 ——> 合并

1、初始化如下图，fa[]存储每个元素的父节点，初始化时每个父节点设置为自己。

2、查找如下图，找到i的祖先；

 3、合并如下图，i的祖先指向j的祖先

最后将一些不相干的集合进行了合并。另外如果要进行路径压缩，则find函数查找祖先元素进行了路径压缩。

备注：如果觉得写的有问题敬请指出，请大家以自己的判断力来了解并查集算法，毕竟我也是初步了解阶段，在此记录一下学习过程。

并查集参考文献：

1、并查集算法详解 - 知乎

2、并查集从入门到出门 - 力扣（LeetCode）

3、图论——并查集(详细版)_哔哩哔哩_bilibili