# [LeetCode] Longest Consecutive Sequence 求最长连续序列

+关注继续查看

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.

C++ 解法一：

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_set<int> s(nums.begin(), nums.end());
for (int val : nums) {
if (!s.count(val)) continue;
s.erase(val);
int pre = val - 1, next = val + 1;
while (s.count(pre)) s.erase(pre--);
while (s.count(next)) s.erase(next++);
res = max(res, next - pre - 1);
}
return res;
}
};

Java 解法一：

public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Set<Integer> s = new HashSet<Integer>();
for (int num : nums) s.add(num);
for (int num : nums) {
if (s.remove(num)) {
int pre = num - 1, next = num + 1;
while (s.remove(pre)) --pre;
while (s.remove(next)) ++next;
res = Math.max(res, next - pre - 1);
}
}
return res;
}
}

C++ 解法二：

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_map<int, int> m;
for (int d : nums) {
if (!m.count(d)) {
int left = m.count(d - 1) ? m[d - 1] : 0;
int right = m.count(d + 1) ? m[d + 1] : 0;
int sum = left + right + 1;
m[d] = sum;
res = max(res, sum);
m[d - left] = sum;
m[d + right] = sum;
}
}
return res;
}
};

Java 解法二：

public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int num : nums) {
if (m.containsKey(num)) continue;
int left = m.containsKey(num - 1) ? m.get(num - 1) : 0;
int right = m.containsKey(num + 1) ? m.get(num + 1) : 0;
int sum = left + right + 1;
m.put(num, sum);
res = Math.max(res, sum);
m.put(num - left, sum);
m.put(num + right, sum);
}
return res;
}
}

[LeetCode] Longest Line of Consecutive One in Matrix 矩阵中最长的连续1
Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
1005 0
[LeetCode] Binary Tree Longest Consecutive Sequence
Problem Description: Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from so...
645 0
SAP Spartacus Focusdirective继承自Lockdirective，静态代码分析
SAP Spartacus Focusdirective继承自Lockdirective，静态代码分析
0 0
SAP Spartacus LockFocusDirective
SAP Spartacus LockFocusDirective
0 0
+关注