⚔ LeetCode | 128. Longest Consecutive Sequence

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 128. Longest Consecutive Sequence

Difficulty : Hard

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example 1:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Analysis

这道题的题意是需要我们在给定的无序数组中找出最大的连续序列的长度。

一看上去似乎挺简单的，只要简单的排个序然后遍历一遍就可以得到答案。但是题目还有一个附加要求，就是需要在 O(n)的时间复杂度里面完成，这样就需要一些特别的技巧呐。

Approach 1

要在 O(n)的时间内找出最长的连续序列的长度，就需要充分利用信息，对于给定的数据只能进行常数次访问。

这里使用了HashMap或UnionSet之类的数据结构，使得可以用 O(1)的代价检测数据中是否存在某个值。

具体过程:

  • 把输入的的数据全部插入到Set里面。

  • 对于Set中的每一个值，判断其前一个值是否也在Set中

    • 如果在，就证明这个值并不是一个序列的最开始的值，因此可以跳过
    • 如果不存在，就说明这个值是一个序列的开端，然后判断其后一个值是否也在Set中，直到找到一个不在Set中的值，这个就是这个序列的末端。这样我们就得知了一个序列的长度。

  • 遍历每一个值后，记录下过程中得到的序列的最长长度。

我们来看看题目的例子：

[100, 4, 200, 1, 3, 2]

对于100，不存在99，因此这是一个序列的开端，扫描后续，得到这个序列的长度为1

对于4，存在3，因此这并不是一个序列的开端，跳过

对于200，不存在199，因此这是一个序列的开端，扫描后续，得到这个序列的长度为1

对于1，不存在0，因此这是一个序列的开端，扫描后续，得到这个序列的长度为4

对于3，存在2，因此这并不是一个序列的开端，跳过

对于2，存在1，因此这并不是一个序列的开端，跳过

最后，得到最长序列长度为 4

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet;
        for(int num : nums) {
            numSet.insert(num);
        }
        int maxSeqLen = 0;
        for(int num : numSet) {
            if (numSet.find(num - 1) == numSet.end()) {
                int currentLen = 1;
                int currentNum = num;
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentLen++;
                    currentNum++;
                }
                if (currentLen > maxSeqLen) {
                    maxSeqLen = currentLen;
                }
            }
        }
        return maxSeqLen;
    }
};

以上的代码有两个for，并且其中一个for里面还有一个while，一看上去时间复杂度就不低，当其实这个算法的时间复杂度也是O(n)

对于以上的算法，每个值首先要查询其前一个值是否存在，复杂度为O(n + n)，然后有两种不同的状态：

  • 序列的开端：最多扫描一次整个序列，复杂度为O(n)
  • 非序列的开端：直接跳过

因此，数组中的每一个值，最多被扫描 3 次，因此最大的时间复杂度也就O(3n)，可以看作为O(n)

而空间复杂度也是O(n)

Summary

这个算法看上去代码很短，其实是依赖于HashMap之类的数据结构的，如果要手动编写一个这样的数据结构代码行数也低不到哪里去。因此，很多算法都是依赖于一些特殊的数据结构的，数据结构对于算法的重要性就不言而喻了。

土豪通道
0%