0386. Lexicographical Numbers
=============================
题目信息
--------
:题号: 0386
:难度: Medium
:主题: 整数范围、十进制字典序、完整输出、复杂度要求
:原题: `LeetCode 0386 `_
:重点: 返回 1 到 n 的全部整数、比较依据是十进制文本字典序、要求线性时间和常数级辅助空间
题目重述
--------
给定正整数 ``n``,返回闭区间 ``[1, n]`` 中的全部整数,并按照它们不带前导零的十进制表示进行字典序排列。例如在字典序中,前缀 ``1`` 后面先出现 ``10``、``100`` 等,再轮到 ``2``。
``n`` 位于 ``[1, 5 * 10^4]``。结果必须恰好包含每个整数一次。题目要求总时间复杂度为 ``O(n)``,除返回数组外只使用常数级额外空间;不能通过把全部整数转为字符串后整体排序来绕开该要求。
自建示例
--------
两位数进入前缀顺序:
.. code-block:: text
输入:n = 12
输出:[1,10,11,12,2,3,4,5,6,7,8,9]
解释:按十进制字符串比较时,"10"、"11"、"12" 都以 "1" 开头,因此排在 "2" 之前。
范围只有两个整数:
.. code-block:: text
输入:n = 2
输出:[1,2]
解释:结果包含区间内每个整数一次,二者字典序与数值顺序相同。
把十进制前缀当作一棵树
------------------------
数字的字典序遍历可以看成前缀树的先序遍历:从 ``1`` 开始,若当前数乘 10 仍不超过 ``n``,就进入它的下一位子节点;否则说明当前分支已经走到底,沿父节点回退,直到可以把当前前缀加 1。回退时跳过末位为 9 或已经超过 ``n`` 的前缀。
该过程直接在整数前缀上移动,不建立字符串,也不使用额外的访问集合;每个整数输出一次,回退和扩展的总移动次数与输出规模同阶。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector lexicalOrder(int n) {
std::vector result;
result.reserve(n);
long long current = 1;
for (int i = 0; i < n; ++i) {
result.push_back(static_cast(current));
if (current * 10 <= n) {
current *= 10;
} else {
while (current % 10 == 9 || current + 1 > n) {
current /= 10;
}
++current;
}
}
return result;
}
};
代码分析
--------
乘 10 相当于进入当前前缀的最小子树,除以 10 相当于回到父前缀;``current`` 使用宽类型避免中间乘 10 溢出。除返回数组外只使用常数级状态,输出本身占 ``O(n)``,总遍历时间为 ``O(n)``。