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)``。