题目大意：
最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=128
解题思路分析：
这道题的本质是要给数字分组，只要是相差为1的数字都要被分到一个组，需要注意的是每组数据中不能有重复的数字。解决分组问题的最好办法是使用Union-Find并查集，解题步骤大致如下：
- 先建立一个root数组，表示每个数字的组号（根节点下标），初始时，每个数字自己一组，即root[i]=i。
- 建立一个map，循环每一个数字，利用map记录已经出现过的数字，key为数字，value为该数字的下标。如果当前数字在map中存在，说明该数字为重复数字，可以跳过。然后查看该数字加一的值是否在map中存在过，如果存在，则将该数字与当前数字做Union操作（将一个数字的根节点连接到另一个数字的根节点上，使得2个数字的根节点相同，即表示为同一组），同理如果map中存在当前数字减一，也将这两个数字进行Union操作。
- 最后循环一遍root数组，查看每个数字的根，统计相同根的个数最多的即是返回结果。
实现代码：
int[] root; // 分组用的数组
public int longestConsecutive(int[] nums) {
// 初始化root数组
root = new int[nums.length];
// 初始化时，每个数字自己一组
for(int i=0;i<nums.length;i++) root[i]=i;
// 记录出现过的数字
Map<Integer,Integer> map = new HashMap();
// 循环每个数字
for(int i=0;i<nums.length;i++){
// 当前数字
int n=nums[i];
// 如果当前数字在map中存在，说明是重复数字，跳过
if(map.containsKey(n)) continue;
// 如果map中存在当前数字减一，Union该数字与当前数字
if(map.containsKey(n-1)) union(i, map.get(n-1));
// 如果map中存在当前数字加一，Union该数字与当前数字
if(map.containsKey(n+1)) union(i, map.get(n+1));
// 将当前数字与下标存入map
map.put(n,i);
}
// 返回结果
int res=0;
// 统计同根的数字个数
int[] count = new int[nums.length];
for(int i=0;i<nums.length;i++){
// 找到当前数字的根
int root=root(i);
// 当前根下的数字加一，同时更新返回结果最大值
res=Math.max(res, ++count[root]);
}
return res;
}
// 查找根（Find）
int root(int index){
// 根元素的特点是下标等于值
while(index!=root[index]){
index=root[index];
}
return index;
}
// 合并两个数字下标
void union(int index1, int index2){
// 将index2的根连接到index1的根下
root[root(index1)] = root(index2);
} 本题解法执行时间为7ms。
Runtime: 7 ms, faster than 61.06% of Java online submissions for Longest Consecutive Sequence.
Memory Usage: 36.8 MB, less than 98.28% of Java online submissions for Longest Consecutive Sequence.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-128-longest-consecutive-sequence-解题思路分析/