首页 > 代码库 > 【leetcode刷题笔记】Longest Consecutive Sequence

【leetcode刷题笔记】Longest Consecutive Sequence

2024-07-12 18:00:03   223人阅读

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.

 

题解：首先构建一个hashmap，键值为num中的所有元素，这样查找一个元素是否在num中就只需要O(1)的时间了。

接下来以上面给定的例子来说明算法：

比如上述num数组中第一个元素是100，那么就找101或者99在不在num中，发现不在；

num中第二个元素是4，那么就找3或者5是否在num中，发现3在num中，而5不在；于是继续找2在不在num中，然后找1在不在num中.....最终知道有4，3，2，1这么一个长度为4的序列。在这个遍历过程中，因为已经找到了序列4，3，2，1，所以如果以后遍历到3的时候再找到的序列3，2，1已经没有意义了（肯定比当前的最长序列短），所以3，2，1这三个元素在未来的遍历中，我们都不需要考虑了，这里就把它们在hashmap中对应的值改成1，作为标志。

num中第三个元素是200，那么就找199或者201是否在num中，发现都不在；

num中还有元素1，3，2，基于上述描述的原因，就不再遍历了。

这样就保证了每个元素最多遍历一次，时间复杂度为O(n)。

示例图如下;

代码如下：

 1 public class Solution { 2     public int longestConsecutive(int[] num) { 3         int answer = 0; 4         HashMap<Integer, Integer> map = new HashMap<Integer,Integer>(); 5          6         for(int i:num) 7             map.put(i, 0); 8          9         for(int i:num){10             if(map.get(i) == 1)11                 continue;12             13             int currMax = 1;14             int tmp = i-1;15             //left16             while(map.containsKey(tmp)){17                 map.put(tmp, 1); //we have visited tmp,so we don‘t start with tmp in the future18                 currMax++;19                 tmp--;20             }21             22             tmp = i+1;23             while(map.containsKey(tmp)){24                 map.put(tmp, 1);25                 currMax++;26                 tmp++;27             }28             29             if(currMax > answer)30                 answer = currMax;31         }32         return answer;33     }34 }


联系
我们