https://oj.leetcode.com/problems/longest-consecutive-sequence/
http://blog.csdn.net/linhuanmars/article/details/22964467
public class Solution {
public int longestConsecutive(int[] num) {
// Solution A:
// return longestConsecutive_Sort(num);
// Solution B:
return longestConsecutive_Graph(num);
}
///////////////
// Solution B: Graph
//
private int longestConsecutive_Graph(int[] n)
{
// 把这n个数 构建成一个 graph
// 如果 两个数 相差 1， 他们相连
//
// 建立 一个set
// 取 1 点 ， bfs 它， 更新max
// bfs完成， 如果set 还有其他点 取下一点
Set<Integer> set = new HashSet<>();
for (int i : n)
set.add(i);
int max = 1;
while (!set.isEmpty())
{
// Get a random point.
int i = set.iterator().next();
int curlen = 1;
set.remove(i);
// BFS it
int j = i + 1;
while (set.contains(j))
{
curlen ++;
set.remove(j);
j ++;
}
j = i - 1;
while (set.contains(j))
{
curlen ++;
set.remove(j);
j --;
}
max = Math.max(max, curlen);
}
return max;
}
///////////////
// Solution A: Sort
//
private int longestConsecutive_Sort(int[] n)
{
Arrays.sort(n);
int max = 1;
int cur = 1;
for (int i = 0 ; i < n.length - 1 ; i ++)
{
if (n[i + 1] - n[i] == 1)
{
cur ++;
max = Math.max(max, cur);
}
else if (n[i + 1] == n[i])
{
continue;
}
else
{
cur = 1;
}
}
return max;
}
}[LeetCode]128 Longest Consecutive Sequence
原文：http://7371901.blog.51cto.com/7361901/1600342