P2 最长连续序列 LeetCode128

P2最长连续序列，难度困难，主要标签为并查集、数组。

题目

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

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

示例:

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

LeetCode题目链接https://leetcode-cn.com/problems/longest-consecutive-sequence/

---

解题思路

具体思想见注释。

1. 将输入的数组加入到集合中去重。
2. 遍历数组，当前为num，判断num-1是否在集合中，当num-1不在集合中，num则为连续序列第一个数，开始计数，直到num+1不在集合中，此时count计数器的值即为从num开始的连续最长序列的长度。

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {  //去重
        	set.add(nums[i]);
        }
        int seqlen = 0;
        for (int i = 0; i < nums.length; i++) {
        	int num = nums[i];
        	if (set.contains(num-1) == false) {  //对num，如果num-1不在set中，从num开始计数
        		int count = 1;
        		while (set.contains(num+1)) {  //num+1在set中，count++
        			count++;
        			num = num + 1;
        		}
        		seqlen = Math.max(seqlen, count);
        	}
        }
        return seqlen;
    }
}

测试主函数：

import java.util.HashSet;


public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		int[] nums = {100, 4, 200, 1, 3, 2};
		int n = s.longestConsecutive(nums);
		System.out.print(n);
	}

}

输出：

4

本文作者： Yao Zhu
发布时间： 2019-08-29
最后更新： 2019-08-31
本文链接： https://juoyo.github.io/posts/30288ee6.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信