哈希--128. 最长连续序列/medium 理解度B

cjh-Java

已于 2024-04-25 17:12:53 修改

阅读量416

点赞数 8

分类专栏： # 算法解题报告-leetcode 热门文章标签：哈希算法数据结构算法

于 2024-01-23 07:30:00 首次发布

本文链接：https://blog.csdn.net/fujuacm/article/details/135692687

版权

算法解题报告-leetcode 热门专栏收录该内容

60 篇文章

订阅专栏

128. 最长连续序列

1、题目
2、题目分析
3、复杂度最优解代码示例
4、适用场景

1、题目

给定一个未排序的整数数组 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

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

2、题目分析

一批数据按连续性分成了多段，查找最长分段的长度。
（使用分段处理的思路，遇到段头再开始处理，其他元素直接返回。这里的关键是：判断某元素是否为所在段的段头）

注：如何判断某元素是否为所在分段开头位置：判断该元素-1的数是否存在于哈希表，若不存在，则该元素是所在分段开头位置

将数据都存在哈希表中，
遍历数组，只要遇到该元素是所在分段的开头位置，则遍历该段的长度。
若该元素不是所在分段的开头位置，则忽略。

3、复杂度最优解代码示例

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            // 标记元素是否存在
            set.add(num);
        }

        int maxLength = 0;

        for (int num : set) {
            if (set.contains(num - 1)) {
                // 当前元素非段头元素，不处理
                continue;
            }

            // 遇到段头元素，开始遍历所在段，并记录段长
            int length = 1;
            while (set.contains(num + length)) {
                length++;
            }
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }