leet code 128. 最长连续序列

128. 最长连续序列

题目描述

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

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

示例 1：

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

提示：

题目解析

题目要求 O(n) 的时间复杂度解决此问题，但是没有头绪。先忽略这个限制

• 笨方法对数组进行排序
• 然后再进行遍历

时间复杂度 O(logN)

public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int ans = 0,idx = 0,n = nums.length;
        while(idx < n) {
            // 定义下一个下标位置
            int step = idx + 1;
            // 记录长度，初始化1 是因为最小为 1
            int cnt = 1;
            while(step < n) {
                // 连续的情况.
                if(nums[step] == nums[step - 1] + 1) {
                    cnt++;
                    step++;
                } else if(nums[step] == nums[step - 1]) {
                    // 相等的情况.
                    step++;
                } else if(nums[step] > nums[step - 1] + 1) {
                    // 跳出循环的情况.
                    break;
                }
            }
            ans = Math.max(ans, cnt);
            idx = step;
        }
        return ans;
    }

• 经过复杂的解法，发现有了一点思路
• 可以使用map集合来保存当前元素对应的 连续子序列 的长度
• 然后不断更新
• 遍历到一个元素，只需要判断 其本身、其本身减一和其本身加一 是否存在于 哈希表中即可

• 然后分别进行对应的逻辑计算.

code 尝试 O(N)

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            if (map.containsKey(num)) {
                continue;
            } else {
                int before = num - 1;
                int next = num + 1;
                if (map.containsKey(before) || map.containsKey(next)) {
                    int beforeLen = map.getOrDefault(before, 0);
                    int nextLen = map.getOrDefault(next, 0);
                    int len = beforeLen + nextLen + 1;
                    map.put(num, len);
                    //  这里的  while 更新会导致超时
                    while (map.containsKey(before) && map.get(before) != len) {
                        map.put(before, len);
                        before--;
                    }
                    while (map.containsKey(next) && map.get(next) != len) {
                        map.put(next, len);
                        next++;
                    }
                } else {
                    map.put(num, 1);
                }
                ans = Math.max(ans, map.get(num));
            }
        }
        return ans;
    }
}

• 测试发现会超时

O(N) 解法

• 通过哈希表的方式，发现 数组内连续的子序列可以归属到一个集合中去
• 刚刚好适合用并查集来解决问题
• 以数组 nums = [100, 4, 200, 1, 3, 2]为例
• 只需要遍历一次数组+利用哈希表
• 遍历到当前元素的时候

• 首先判断是否在哈希表中存在，如果存在不重复处理
• 然后 判断其 加一 和 减一 的值是否在哈希表中存在
• 如果存在则 进行并查集合并操作
• 如上图，遍历到 元素3 哈希表中存在 4，则 元素 3和4所对应的集合进行合并
• 遍历到元素2 元素1和3在哈希表中存在，则 合并其所在的集合
• 利用并查集的特性，求出元素最多的集合直接返回

show code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        // 首先定义一个哈希表
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化并查集.
        Union union = new Union(nums.length);

        // 开始遍历nums
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                continue;
            }
            int less = num - 1;
            int up = num + 1;
            if (map.containsKey(less) || map.containsKey(up)) {
                // 表示当前元素可以构成一个长度大于1 的子序列.
                if (map.containsKey(less)) {
                    union.union(map.get(less), i);
                }
                if (map.containsKey(up)) {
                    union.union(map.get(up), i);
                }
            }
            map.put(num, i);
        }

        return union.max;
    }
}

class Union {

    public int count;
    public int[] arr;
    // sz[i] 表示以 i 为根集合中的元素个数
    public int[] sz;

    public int max;

    public Union(int count) {
        this.count = count;
        arr = new int[count];
        sz = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = i;
            // 初始化1个.
            sz[i] = 1;
        }
        max = 1;
    }

    public int find(int val) {
        // 不断查询自己的父节点，直到到达根节点
        while (val != arr[val]) {
            val = arr[val];
        }
        return val;
    }

    public boolean isConnected(int a, int b) {
        return find(a) == find(b);
    }

    public void union(int a, int b) {
        // rootA、rootB 分别表示  a b 所属的集合编号.
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) {
            // 表示同一个集合
            return;
        }
        max = Math.max(max, sz[rootA] + sz[rootB]);
        if (sz[rootA] < sz[rootB]) {
            // 元素个数少的集合  合并到 元素个数多的集合
            // 这里 a 向 b 合并
            arr[rootA] = rootB;
            // b 集合的元素个数增加
            sz[rootB] += sz[rootA];
        } else {
            arr[rootB] = rootA;
            sz[rootA] += sz[rootB];
        }
    }

}