- 浏览: 174219 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
题目要求我们用O(n)的时间复杂度来解决,我们可以采用并查集的思想,当扫描到一个元素,我们从当前元素的两边开始处理,如果连续的都进行标记,同时维护一个最大值,再次扫描的时候如果被标记过的就可以跳过,这样我们就可以在O(n)的时间复杂度下找到最长的连续序列。代码如下:
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.
题目要求我们用O(n)的时间复杂度来解决,我们可以采用并查集的思想,当扫描到一个元素,我们从当前元素的两边开始处理,如果连续的都进行标记,同时维护一个最大值,再次扫描的时候如果被标记过的就可以跳过,这样我们就可以在O(n)的时间复杂度下找到最长的连续序列。代码如下:
public class Solution { public int longestConsecutive(int[] nums) { if(nums == null) return 0; HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); int max = 1; for(int i : nums) hm.put(i, 0); for(int i = 0; i < nums.length; i++) { int count = 1; int left = -1; int right = 1; if(hm.get(nums[i]) == 1) continue; hm.put(nums[i], 1); while(hm.containsKey(nums[i] + left)) { hm.put(nums[i] + left, 1); count ++; left --; } while(hm.containsKey(nums[i] + right)) { hm.put(nums[i] + right, 1); count ++; right ++; } max = Math.max(max, count); } return max; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 228Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 231You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 345Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 337Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 458Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 520Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 434Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 623Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 432The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 391Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 522Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 537Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 374All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 866Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 884Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 558Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 604Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 738You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 635For a undirected graph with tre ...
相关推荐
Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...
LMS Longest Monotonically Increasing Sequence Algorithm
Longest Consecutive Sequence Two Sum 3Sum 3Sum Closest 4Sum Remove Element Move Zeroes Next Permutation Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set ...
前端工程师面试
java lru leetcode SDE-问题 标准 SDE 问题列表 第一天:(数组) 日 问题陈述 解决方案 困难 使用的数据结构 使用的算法 时间复杂度 空间复杂度 ...Longest Consecutive Sequence Longest Subarray w
leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: ...Consecutive Sequence Longest Subarray with 0 sum 给定
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
最长连续序列 描述 给定一个未排序的整数数组,请找出最长的连续元素序列的长度。 好吧,假设该任务仅与步长等于1的序列有关。 例如: 给定exampleArray = [100, 4, 200, 1, 3, 2] 100,4,200,1,3,2 [100, 4, ...
给定两个序列X={X1, X2,···,Xm}和Y={Y1, Y2,···,Yn},找出X和Y的最长公共子序列(Longest Common Sequence)。 比如字符串X:{BDCABA};字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
关于Longest Common Subsequences演算法
java解决动态规划中最长公共子序列(longest common sequence)问题
Codewars实践 解决方案 3k 问题/卡塔 解决方案 4k 问题/卡塔 解决方案 5k 问题/卡塔 解决方案 6- 问题/卡塔 解决方案 7- 问题/卡塔 解决方案
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
为此,针对代码同源性检测结构化匹配进行了研究,在LCS(longest common sequence)算法中融入了跳变信息保留、结构边界划分、窗口搜索、计数重置、有效序列界定等逻辑,用于Token摘要的结构化信息匹配,提出了一种...
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
最长公共子序列演示程序,算法分析与设计,动态规划算法
求最长公共子序列,求最长公共子序列!!!