128、最长连续子序列

leetcode 并查集数组哈希

Created At : 2020-07-26 00:19

Count:731 Views 👀 :

Comment:

题目
1. 示例:
题解

题目

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

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

链接：https://leetcode-cn.com/problems/longest-consecutive-sequence

示例:

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

题解

1、利用集合

遍历一边哈希表存储已经出现过的数字，然后在遍历一边，求每个数字的最大连续子序列，更新最长的结果。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 集合
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int longestLen = 0;
        for (int num : nums) { // 针对num 求 num最大子序列的长度
            // num - 1 不存在，之前断了，可以开始新一轮的求最长连续数字
            if (!numSet.contains(num - 1)) {
                int curNum = num;
                int curLen = 1;
                // 累加求连续子序列
                while(numSet.contains(curNum + 1)){
                    curNum++;
                    curLen++;
                }

                // 不连续了，退出了循环，则更新最大值
                longestLen = Math.max(longestLen, curLen);
            }
        }
        return longestLen;
    }
}

2、排序+遍历

先排序，相当于原地hash。
然后双指针，遍历每个元素，求当前的最长连续子序列，更新每次的结果，直到到达数组尾部。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 边界case
        if(nums.length <= 1){
            return nums.length;
        }

        Arrays.sort(nums);
        int max = 1;
        int temp = 1;
        int head = nums[0];

        for(int i=1;i < nums.length;i++){
            // 这里更新累加求连续数字子串
            if(nums[i] == head + 1){
                temp++;
            }else {
                // 重置
                if(nums[i] != head){
                    temp = 1;
                }
            }
            // 
            if(temp > max){
                max = temp;
            }
            // 更新头
            head = nums[i];
        }
        return max;
    }
}

并查集

并查集本质上是图的连通域
并查集数据结构，可以快速查找两链接的节点，根据题目需求，同时记录并查集的

public class Solution {
    // 使用HashMap来存储每个节点的root
    HashMap<Integer, Integer> fa = new HashMap<>();
    // 使用HashMap来存储以当前节点为root的节点数量
    HashMap<Integer, Integer> size = new HashMap<>();
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int ans = 0;

        // 初始化fa 和 size
        for (int num : numSet) {
            fa.put(num, num);
            size.put(num, 1);
        }

        // 遍历数组，当满足合并关系时，执行merge操作
        for (int num : numSet) {
            // num + 1 存在 则链接起来
            if (numSet.contains(num + 1)) {
                merge(num, num + 1);
            }
        }

        // 取最大值作为结果
        for (int num : size.values()) {
            ans = Math.max(ans, num);
        }
        return ans;
    }

    // find函数，用于查找节点的roo
    private int find(int x) {
        if (!fa.containsKey(x)) {
            return -1;
        }
        // 递归查找根节点
        if (fa.get(x) != x) {
            fa.put(x, find(fa.get(x)));
        }
        return fa.get(x);
    }

    // merge函数，用于合并两个节点
    private void merge(int f, int to) {
        int rootF = find(f);
        int rootTo = find(to);
        // 还没接通起来
        if (rootF != rootTo) {
            // 连通
            fa.put(rootF, rootTo);
            // 更新size
            size.put(rootTo, size.get(rootTo) + size.get(rootF));
        }
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com