问题描述:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2]
,
The longest consecutive elements sequence is [1, 2, 3, 4]
. Return its length: 4
.
Your algorithm should run in O(n) complexity.
原问题链接:https://leetcode.com/problems/longest-consecutive-sequence/
问题分析
这个问题看起来确实有点难度,因为这个序列是没有排序的。如果我们需要去找它这里面元素能构成的最大序列,一种最简单的办法确实是对这个数组排序。但是一般来说,排序的时间复杂度就到了O(nlogn)了,而这里要求的时间复杂度为O(n)。所以上述的办法并不可行。
既然上面方法不可行的话,我们就看看有没有别的办法。在数组里,我们可以将每个元素和它是否被访问过的标记放到一个Map<Integer, Boolean>里。这样所有的元素最开始对应的值都是false。而每次我们遍历元素数组的时候,就尝试从元素的两头分别递增和递减,如果递增或者递减后也有元素存在于map中,说明它们构成了一个连续的序列。在每次访问完一个元素之后,我们要将元素在map里对应的值设置为true,这样可以防止后面的元素再重复访问这个位置。我们就可以跳过一些不必要的比较。
按照这个过程,我们整体的时间复杂度也可以降下来。详细的实现如下:
public class Solution { public int longestConsecutive(int[] nums) { if(nums == null || nums.length == 0) return 0; int maxLen = 1; Map<Integer, Boolean> map = new HashMap<>(); for(int i : nums) map.put(i, false); for(int i = 0; i < nums.length; i++) { int right = nums[i] + 1, n = nums[i], count = 0; while(map.containsKey(n) && !map.get(n)) { map.put(n, true); n--; count++; } while(map.containsKey(right) && !map.get(right)) { map.put(right, true); right++; count++; } maxLen = Math.max(maxLen, count); } return maxLen; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 Leetcode代码题解 随缘刷题,选择性更新题解 LeetCode 94 144 145 ...longest-consecutive-sequence 最长连续序列: Leetcode 155 Min Stack 最小栈: LeetCode 773 滑动谜题: ......
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
LeetCode 101:和你一起你轻松刷题(C++)
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题