0386. Lexicographical Numbers

题目信息

题号:

0386

难度:

Medium

主题:

整数范围、十进制字典序、完整输出、复杂度要求

原题:

LeetCode 0386

重点:

返回 1 到 n 的全部整数、比较依据是十进制文本字典序、要求线性时间和常数级辅助空间

题目重述

给定正整数 n,返回闭区间 [1, n] 中的全部整数,并按照它们不带前导零的十进制表示进行字典序排列。例如在字典序中,前缀 1 后面先出现 10、100 等,再轮到 2。

n 位于 [1, 5 * 10^4]。结果必须恰好包含每个整数一次。题目要求总时间复杂度为 O(n),除返回数组外只使用常数级额外空间;不能通过把全部整数转为字符串后整体排序来绕开该要求。

自建示例

两位数进入前缀顺序:

输入:n = 12
输出:[1,10,11,12,2,3,4,5,6,7,8,9]
解释:按十进制字符串比较时,"10"、"11"、"12" 都以 "1" 开头,因此排在 "2" 之前。

范围只有两个整数:

输入:n = 2
输出:[1,2]
解释:结果包含区间内每个整数一次,二者字典序与数值顺序相同。

把十进制前缀当作一棵树

数字的字典序遍历可以看成前缀树的先序遍历:从 1 开始,若当前数乘 10 仍不超过 n,就进入它的下一位子节点;否则说明当前分支已经走到底,沿父节点回退,直到可以把当前前缀加 1。回退时跳过末位为 9 或已经超过 n 的前缀。

该过程直接在整数前缀上移动,不建立字符串,也不使用额外的访问集合;每个整数输出一次,回退和扩展的总移动次数与输出规模同阶。

C++ 实现

class Solution {
public:
    std::vector<int> lexicalOrder(int n) {
        std::vector<int> result;
        result.reserve(n);
        long long current = 1;
        for (int i = 0; i < n; ++i) {
            result.push_back(static_cast<int>(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)。