首页 > 代码库 > Leetcode | Longest Consecutive Sequence

Leetcode | Longest Consecutive Sequence

2024-07-02 15:46:12   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.

本题是可以用并查集来做，参照之前的摘录：http://www.cnblogs.com/linyx/p/3638222.html

当然也可以用dfs的方式，但是为了O(n)，需要在访问一个元素之后把该元素删掉，删除也需要O(1)，所以用多一个list。

这里的dfs意思是，从数x，去访问x-1,x-2,...，然后访问x+1,x+2,...，边访问边从list删除。这样就需要快速地知道某个数的位置，所以这里用了一个map。

另一点需要注意的是，当从list删除时，map是没有删除的，这里用list.end()来表示某个数已经被删除了，删掉的数就不会再被判断。也就是说，下一次访问到已经访问过的数，或者重复的数，那么map里已经更新为list.end()，所以不会再从这里去dfs，这样保证了不会再删一遍。

首先，每个元素，要么dfs，要么没得dfs。dfs是在list上做的，list的长度随着dfs递减，所以整个开销为O(n)。

 1 class Solution {
 2 public:
 3     int longestConsecutive(vector<int> &num) {
 4         if (num.empty()) return 0;
 5         map<int, list<int>::iterator> len;
 6         int n = num.size();
 7         list<int> copy;
 8         for (int i = 0; i < n; ++i) {
 9             copy.push_front(num[i]);
10             len[num[i]] = copy.begin();
11         }
12         int max = 0;
13         for (int i = 0; i < n; ++i) {
14             if (len[num[i]] == copy.end()) continue;
15             int l = 1;
16             while (len.find(num[i] - l) != len.end()) { 
17                 copy.erase(len[num[i] - l]);
18                 len[num[i] - l] = copy.end();
19                 l++;
20             }
21             int u = 1;
22             while (len.find(num[i] + u) != len.end()) {
23                 copy.erase(len[num[i] + u]);
24                 len[num[i] + u] = copy.end();
25                 u++;
26             }
27             if (l + u - 1 > max) {
28                 max = l + u - 1;
29             }
30             len[num[i]] = copy.end();
31         }
32         return max;
33     }
34 };

 


联系
我们