0163. Missing Ranges
====================
题目信息
--------
:题号: 0163. 缺失的区间
:难度: Easy
:主题: 数组、区间、顺序扫描
:原题: `LeetCode 0163 `_
:重点: 将数值域枚举压缩为相邻已知数之间的最大连续空隙,并安全处理两端边界
题目重述
--------
给定闭区间 ``[lower, upper]``,以及一个严格递增且元素都位于该区间内的整数数组
``nums``。区间内没有出现在 ``nums`` 中的整数称为缺失整数。
返回按起点升序排列的最短区间列表,使这些闭区间恰好覆盖全部缺失整数:不能覆盖
``nums`` 中已有的数,也不能遗漏或重复覆盖缺失整数。每个结果项用 ``[start, end]``
表示,单个缺失数 ``x`` 也表示为 ``[x, x]``。
自建示例
--------
.. code-block:: text
输入:nums = [0,1,3,50,75], lower = 0, upper = 99
输出:[[2,2],[4,49],[51,74],[76,99]]
已知数把目标区间切成四段非空空隙;相邻的缺失数必须合并,才能得到最短列表。
.. code-block:: text
输入:nums = [], lower = -3, upper = -1
输出:[[-3,-1]]
没有任何已知数时,整个目标区间都是一个连续缺失段。
.. code-block:: text
输入:nums = [-1], lower = -1, upper = -1
输出:[]
唯一候选值已经出现,没有缺失区间。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
public:
std::vector> findMissingRanges(
std::vector& nums, int lower, int upper) {
std::vector> missing;
long long next_missing = lower;
for (int value : nums) {
if (next_missing < value) {
missing.push_back({static_cast(next_missing), value - 1});
}
next_missing = static_cast(value) + 1;
}
if (next_missing <= upper) {
missing.push_back(
{static_cast(next_missing), upper});
}
return missing;
}
};
题解
----
原始搜索空间为什么不合适
~~~~~~~~~~~~~~~~~~~~~~~~
最直接的想法是在 ``lower`` 到 ``upper`` 之间逐个枚举整数,判断它是否出现在
``nums`` 中,再把连续缺失值合并。这样确实严格遵循定义,但工作量取决于数值区间宽度
``upper - lower + 1``,而不是输入数组长度。即使 ``nums`` 只有几个数,宽阔区间也会
产生大量“这个值仍然缺失”的重复判断。
题目已经给出更强的信息:``nums`` 严格递增。已知数之间不可能再藏着别的已知数,
因此缺失答案只可能出现在三类位置:第一个已知数之前、相邻已知数之间、最后一个已知数
之后。无需访问缺失区间里的每个值,只要确定每段空隙的两个端点。
把已覆盖前缀压缩成一个状态
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
令 ``next_missing`` 表示“当前尚未被处理的最小整数”。初始为 ``lower``。扫描到已知数
``value`` 时:
* 若 ``next_missing < value``,那么从 ``next_missing`` 到 ``value - 1`` 没有任何
已知数,整段都是缺失区间;
* 若 ``next_missing == value``,当前最小候选恰好已存在,没有空隙需要输出;
* 处理完 ``value`` 后,将状态推进到 ``value + 1``。
由于输入严格递增且都在目标区间内,不会出现 ``next_missing > value`` 的有效扫描状态。
循环结束后,若 ``next_missing <= upper``,尾部尚未处理的部分整体构成最后一个缺失区间。
这个状态把“从上一个已知数之后到哪里为止”所需的历史压缩为一个整数,不需要额外集合,
也不需要给数组插入哨兵。
最短列表为何自然得到
~~~~~~~~~~~~~~~~~~~~
每次输出的 ``[next_missing, value - 1]`` 左侧紧邻区间边界或前一个已知数,右侧紧邻
当前已知数,因此它已经是一个不能继续扩展的最大连续缺失段。不同输出之间至少隔着一个
``nums`` 中的已知数,无法合并;而一段内部若再拆开,只会增加区间数量。
所以扫描既不会漏掉缺失数,也不会覆盖已知数,并且恰好为每个最大连续缺失段输出一次,
由此得到题目要求的最短列表。
具体走读
~~~~~~~~
对 ``nums = [0,1,3,50,75]``、``[lower,upper] = [0,99]``:
#. ``next_missing = 0``。遇到 0、1 时都没有空隙,状态依次推进为 1、2;
#. 遇到 3,``2 < 3``,输出 ``[2,2]``,再令状态为 4;
#. 遇到 50,输出 ``[4,49]``;遇到 75,输出 ``[51,74]``,状态变为 76;
#. 扫描结束且 ``76 <= 99``,补上尾部 ``[76,99]``。
若 ``nums`` 为空,循环不执行,初始的 ``next_missing = lower`` 会让整个
``[lower,upper]`` 作为尾部空隙输出。若数组已经覆盖目标区间内的每个整数,状态最终为
``upper + 1``,尾部条件失败,答案为空。
溢出边界
~~~~~~~~
若 ``value`` 恰为 32 位最大整数,直接用 ``int`` 计算 ``value + 1`` 会溢出。
``next_missing`` 使用 ``long long``,并在加法前提升 ``value``,让“已处理到上界之后”
仍是一个可表示的状态。写入答案的端点一定处于原始 ``int`` 区间内,因此再转回
``int`` 是安全的。
复杂度
~~~~~~
设 ``nums`` 长度为 ``n``,每个已知数只处理一次,时间复杂度为 ``O(n)``;除返回结果外
只维护 ``next_missing``,额外空间复杂度为 ``O(1)``。答案本身最多包含 ``n + 1`` 段。