题目

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 **O(n)** 且使用 **O(1)** 额外空间的算法。

示例：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

输入：n = 2
输出：[1,2]

解答 & 代码

解法 0：快排

快排，排序时将整数转为字符串进行比较，就是字典序了。
但是时间复杂度不符合题意。

class Solution {
private:
    int partition(vector<int>& nums, int left, int right)
    {
        int randomIdx = rand() % (right - left + 1) + left;
        swap(nums[left], nums[randomIdx]);
        int pivot = nums[left];
        while(left < right)
        {
            while(left < right && to_string(nums[right]) >= to_string(pivot))
                --right;
            nums[left] = nums[right];
            while(left < right && to_string(nums[left]) <= to_string(pivot))
                ++left;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
    void quickSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return;
        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }
public:
    vector<int> lexicalOrder(int n) {
        vector<int> nums(n);
        for(int i = 1; i <= n; ++i)
            nums[i - 1] = i;
        quickSort(nums, 0, n - 1);
        return nums;
    }
};

复杂度分析：设整数 n

时间复杂度 O(nlogn)：快排
空间复杂度 O(n)：数组的长度

执行结果：

执行结果：通过
执行用时：788 ms, 在所有 C++ 提交中击败了 5.12% 的用户
内存消耗：10.1 MB, 在所有 C++ 提交中击败了 95.85% 的用户

解法 1：多叉树 DFS 前序遍历

386. 字典序排数 - O(1) 空间复杂度的迭代方法
多叉树版的递归前序遍历
[中等] 386. 字典序排数 - 图1

class Solution {
private:
    vector<int> result;

    // 深度优先遍历十叉树（当前遍历到的节点值为 num）
    void dfs(int num, int n)
    {
        // 递归结束条件如果当前节点值 num > n，则停止遍历
        if(num > n)
            return;

        // 前序位置：存储当前节点值
        result.push_back(num);
        // 遍历当前节点的所有子节点
        for(int next = num * 10; next < num * 10 + 10; ++next)
            dfs(next, n);
    }   
public:
    vector<int> lexicalOrder(int n) {
        // 第一层从 1 开始遍历（第一位不能是 0）
        for(int num = 1; num < 10; ++num)
            dfs(num, n);
        return result;
    }
};

复杂度分析：设整数 n

时间复杂度 O(n)：遍历每个数
空间复杂度 O(log n)：递归栈深度

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 44.26% 的用户
内存消耗：11.6 MB, 在所有 C++ 提交中击败了 35.43% 的用户

解法 2：多叉树迭代前序遍历

迭代进行前序遍历，通常需要设置额外的栈，但这里：“当前搜索的数 num 本身就能反映出每一层递归的状态，例如当前搜索至 123，我们知道当前层遍历至 3，上一层遍历至 2，再上一层遍历至 1。如果我们需要返回上一层，只需要令 num //= 10 即可”。因此不需要设置额外的栈。

class Solution {
private: 
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        int num = 1;
        while(result.size() < n)
        {
            while(num <= n)                        // 不断进入下一层
            {
                result.push_back(num);
                num = num * 10;
            }
            while(num > n || num % 10 == 9)        // 不断返回上一层
                num = num / 10;
            num += 1;                            // 遍历该层下一个数
        }
        return result;
    }
};

复杂度分析：设整数 n

时间复杂度 O(n)：遍历每个数
空间复杂度 O(1)：

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 73.59% 的用户
内存消耗：10.8 MB, 在所有 C++ 提交中击败了 73.68% 的用户