题目描述

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

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

示例:

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

https://leetcode-cn.com/problems/longest-consecutive-sequence/

解法1

题目要求时间复杂度O(n),那就说明只能扫描一次,排序什么的是不行的。我们可以举个简单的例子,来启发我们寻找合适的算法解决问题。

例1: nums = {1,2,0,5,4,3,-1}

  • 遇到1,那么1独立成一个序列,长度是1;
  • 遇到2,1和2能连在一起成为长度为2的序列{1,2};
  • 遇到0,那么0可以和刚刚{1,2}的序列成为长度为3的连续序列{0,1,2};
  • 遇到5,那么5需要独立成一个序列,长度是1;
  • 遇到4,那么5和4能够接上,形成长度为2的序列{4,5};
  • 遇到3,那么3会将刚刚发现的两个序列{0,1,2}与{4,5}接上,形成{0,1,2,3,4,5},长度为6。
  • 遇到-1,那么-1将会与刚刚形成的序列{0,1,2,3,4,5}连接,形成长度为7的序列{-1,0,1,2,3,4,5}

根据例1,我们可以使用map来记录数字与数字所对应序列的长度。每当添加一个新的数字num,检查num-1与num+1是否存在;如果存在,那么就将左右两部分与新添加的数字num连接起来,形成新的序列。然后更新新序列两端,为新序列的长度。

为什么只需要更新新序列左右两端的值,而不是新序列每一个数字的值?这是因为,序列相联时,只会取端点的值。根据上面的分析,我们能够编写出下面代码。时间复杂度O(n), 空间复杂度O(n)。

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;

        for (int num : nums) {
            if (!map.containsKey(num)) {
                Integer leftLen = map.getOrDefault(num - 1, 0);
                Integer rightLen = map.getOrDefault(num + 1, 0);
                int connectedLen = leftLen + 1 + rightLen;

                res = Math.max(res, connectedLen);

                map.put(num, connectedLen);
                map.put(num - leftLen, connectedLen); // 取到新序列左端点
                map.put(num + rightLen, connectedLen); // 取到新序列右端点
            }
        }

        return res;
    }
}
pwrliang Algorithms, Array

Leave a Reply

Your email address will not be published. Required fields are marked *