0128. Longest Consecutive Sequence
==================================
题目信息
--------
:题号: 0128. 最长连续序列
:难度: Medium
:主题: 数组、哈希集合、连续段、摊还分析
:原题: `LeetCode 0128 `_
:重点: 用集合摆脱原下标顺序,只从连续段唯一左端扩展,使全部内层扫描总量保持线性
题目重述
--------
给定未排序整数数组 ``nums``,找出其中可以组成的最长连续整数序列长度。连续指的是数值依次增加 ``1``,
与元素在原数组中的排列位置无关;重复值不能重复增加长度。空数组返回 ``0``,并要求算法达到 ``O(n)``
时间复杂度。
自建示例
--------
* ``nums = [14, 7, 9, 8, 20, 10, 7, 13, 12]``:连续段有 ``7..10``、``12..14`` 和
``20``,最长长度为 ``4``;第二个 ``7`` 不增加长度;
* ``nums = [1, 2, 0, -1, 8]``:原数组顺序混乱,但数值 ``-1, 0, 1, 2`` 连续,返回 ``4``;
* ``nums = []``:没有连续段,返回 ``0``;
* ``nums = [INT_MIN, INT_MIN + 1, INT_MAX]``:最长长度为 ``2``,边界值的前驱和后继判断不能发生
有符号整数溢出。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
#include
class Solution {
private:
int sortAndScan(std::vector nums) {
if (nums.empty()) {
return 0;
}
std::sort(nums.begin(), nums.end());
int currentLength = 1;
int bestLength = 1;
for (int index = 1; index < static_cast(nums.size()); ++index) {
if (nums[index] == nums[index - 1]) {
continue;
}
if (static_cast(nums[index - 1]) + 1 == nums[index]) {
++currentLength;
} else {
currentLength = 1;
}
bestLength = std::max(bestLength, currentLength);
}
return bestLength;
}
int expandFromEveryValue(const std::vector& nums) {
std::unordered_set values(nums.begin(), nums.end());
int bestLength = 0;
for (int value : values) {
int current = value;
int currentLength = 1;
while (current != INT_MAX && values.count(current + 1)) {
++current;
++currentLength;
}
bestLength = std::max(bestLength, currentLength);
}
return bestLength;
}
int expandOnlyFromStarts(const std::vector& nums) {
std::unordered_set values(nums.begin(), nums.end());
int bestLength = 0;
for (int value : values) {
const bool hasPredecessor =
value != INT_MIN && values.count(value - 1);
if (hasPredecessor) {
continue;
}
int current = value;
int currentLength = 1;
while (current != INT_MAX && values.count(current + 1)) {
++current;
++currentLength;
}
bestLength = std::max(bestLength, currentLength);
}
return bestLength;
}
public:
int longestConsecutive(std::vector& nums) {
return expandOnlyFromStarts(nums);
}
};
题解
----
先去掉原数组顺序这个干扰
~~~~~~~~~~~~~~~~~~~~~~~~
题目寻找的是数值集合中的连续段,而不是原数组中的连续子数组。``[3, 1, 2]`` 能组成 ``1, 2, 3``;
``[1, 1, 2]`` 的两个 ``1`` 也只能代表同一个整数。因此状态只需要回答“值 ``x`` 是否出现”,下标和出现
次数都不是答案所需信息。
方案一:排序后恢复数值顺序
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
最直观的方法复制并排序数组,让相邻数值真正相邻。扫描时跳过重复值;当前值等于前一不同值加一就延长
当前段,否则开始长度为一的新段。``sortAndScan`` 直接、稳定,正确性来自排序后的全序,但排序耗时
``O(n log n)``,没有满足题目希望的线性时间。
方案二:集合查询后继
~~~~~~~~~~~~~~~~~~~~
哈希集合同时完成两次压缩:相同值只保留一份,任意整数是否存在可以期望 ``O(1)`` 查询。于是可以对每个
值不断询问 ``value + 1``、``value + 2`` 是否存在。``expandFromEveryValue`` 得到的每次扩展都是真实连续
段,却仍有隐藏的二次重复:对于长度为 ``k`` 的段,它会从第一个值扫描 ``k`` 个,从第二个扫描 ``k-1``
个,直到段尾,总工作为 ``1 + 2 + ... + k = O(k^2)``。
结构信息:每个连续段只有一个合法起点
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
若 ``x - 1`` 也在集合中,``x`` 一定处于某段内部;从它向右扩展得到的所有内容,都会在该段更小的值启动
时被覆盖。只有前驱不存在的值才可能是完整连续段的左端。因此主解先做前驱测试,内部值直接跳过,只从
唯一左端一路查询后继。
这个判断删除的不是候选答案,而是同一答案的重复入口。任意连续段 ``a, a+1, ..., b`` 都满足:``a-1``
不存在,所以算法一定从 ``a`` 启动;对任意 ``x > a``,``x-1`` 存在,所以不会再次启动。
具体走读
~~~~~~~~
对集合 ``{7, 8, 9, 10, 12, 13, 14, 20}``:
.. list-table::
:header-rows: 1
* - 当前值
- 前驱状态
- 动作
* - ``8``、``9``、``10``
- 前驱存在
- 都是 ``7..10`` 的内部值,跳过
* - ``7``
- ``6`` 不存在
- 扩展 ``7, 8, 9, 10``,长度 ``4``
* - ``12``
- ``11`` 不存在
- 扩展 ``12, 13, 14``,长度 ``3``
* - ``20``
- ``19`` 不存在
- 单点段,长度 ``1``
哈希集合的遍历顺序不确定,不影响结论。即使先看到内部值也只会跳过;段左端迟早会被遍历并负责完整计数。
为何嵌套循环仍是线性
~~~~~~~~~~~~~~~~~~~~
代码表面上有 ``for`` 加 ``while``,但不能简单相乘。每个不同整数要么接受一次前驱检查,要么在所属连续
段从左端扩展时被访问;不同连续段互不重叠。所有 ``while`` 的成功次数之和不超过集合大小,所以构建集合、
外层检查和全部扩展的期望总时间都是 ``O(n)``。
边界状态与代码对应
~~~~~~~~~~~~~~~~~~
``value - 1`` 在 ``value == INT_MIN`` 时会溢出,``current + 1`` 在 ``INT_MAX`` 时同理。主解分别先判断
``value != INT_MIN`` 与 ``current != INT_MAX``,再执行算术;这不是改变连续定义,而是说明 32 位整数域的
两端不可能再有可表示的前驱或后继。排序基线则把加一提升到 ``long long`` 后比较。
``bestLength`` 从零开始,使空集合自然返回零;非空段从长度一开始,再为每个真实后继增加一。公开入口选择
``expandOnlyFromStarts``:它以 ``O(n)`` 额外集合空间换取期望线性时间。排序法适合空间或哈希行为受限的场景,
但时间为 ``O(n log n)``;从每个值扩展只用于暴露重复工作,不应作为实际方案。
复杂度分析
~~~~~~~~~~
主解期望时间 ``O(n)``、空间 ``O(n)``;哈希表极端碰撞时的最坏性能取决于容器实现。排序方案时间
``O(n log n)``,由于代码排序输入副本,工作空间为 ``O(n)``。