题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

样例

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

算法分析

并查集

• 1、通过哈希映射的方式，将数组中 某个位置的元素的值 映射成 当前位置，并存储到哈希表中 即map.put(nums[i], i);
• 2、初始化每个位置的根结点是本身，大小是1，即p[i] = i, size[i] = 1
• 3、枚举所有元素，当枚举到当前元素x时，若哈希表中存在x + 1的元素，则表示这两个元素合并到同一集合中，因此找到x元素的父节点a，x + 1元素的父节点b，并同一把b作为a的父节点，即p[b] = a，且将a负责的集合大小交托到b集合中，即size[b] = size[b] + size[a]

时间复杂度 $O(n)$

Java 代码

class Solution {
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    static int[] p;
    static int[] size;
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        map.clear();
        p = new int[n + 1];
        size = new int[n + 1];
        for(int i = 0;i < n;i ++)
        {
            map.put(nums[i], i);
            p[i] = i;
            size[i] = 1;
        }

        int ans = 1;
        for(int i = 0;i < n;i ++)
        {
            int x = nums[i];
            if(map.containsKey(x + 1))
            {
                int a = find(map.get(x));
                int b = find(map.get(x + 1));
                if(a != b)
                {
                    p[a] = b;
                    size[b] += size[a];
                    ans = Math.max(ans, size[b]); 
                }
            }
        }

        return ans;
    }
}