X

LEETCODE 128. Longest Consecutive Sequence 解题思路分析

题目大意:

最长连续序列

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=128

解题思路分析:

这道题的本质是要给数字分组,只要是相差为1的数字都要被分到一个组,需要注意的是每组数据中不能有重复的数字。解决分组问题的最好办法是使用Union-Find并查集,解题步骤大致如下:

  1. 先建立一个root数组,表示每个数字的组号(根节点下标),初始时,每个数字自己一组,即root[i]=i。
  2. 建立一个map,循环每一个数字,利用map记录已经出现过的数字,key为数字,value为该数字的下标。如果当前数字在map中存在,说明该数字为重复数字,可以跳过。然后查看该数字加一的值是否在map中存在过,如果存在,则将该数字与当前数字做Union操作(将一个数字的根节点连接到另一个数字的根节点上,使得2个数字的根节点相同,即表示为同一组),同理如果map中存在当前数字减一,也将这两个数字进行Union操作。
  3. 最后循环一遍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-解题思路分析/
Categories: leetcode
kwantong: