386. 字典序排数 - 每日一题

386. 字典序排数

难度中等341 收藏 分享 切换为英文 接收动态 反馈

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：

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

示例 2：

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

方法一：递归

利用二叉树的思想。可以将其想成一个10叉树

 /**
     * 利用二叉树的原理
     * @param n
     * @return
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i <= Math.min(9, n); i++) {
            dfs(ans, i, n);
        }
        return ans;
    }

    void dfs(List<Integer> ans, int tmp, int n) {
         if (tmp > n) {
            return;
        }
        ans.add(tmp);
        for (int j = 0; j <= 9; j++) {
            int num = tmp * 10 + j;
            // 加上这个，快很多
            if (num > n) {
                break;
            }
            dfs(ans, num, n);
        }
    }

方法2：深度优先算法

官方答案

image.png

public  List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        int num = 1;
        for (int i = 0; i < n; i++) {
            ans.add(num);
            if (num * 10 <= n) {
                num *= 10;
            } else {
                while (num % 10 == 9 || num + 1 > n) {
                    num /= 10;
                }
                num++;
            }
        }
        return ans;
    }

提示：

• 1 <= n <= 5 * 10<sup>4</sup>