LEETCODE 386. Lexicographical Numbers 解题思路分析

题目大意：

字典序排数

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=386

解题思路分析：

题目要求将1-n的数字按照字典顺序排序，看到字典顺序这几个字我们首先要想到字典树，对于纯数字的字典树，实际上可以想象成一个十叉树，即每个数字下面都有十个子节点。比如数组1下面存在10-19这10个子节点，同理19下面存在190-199这10个子节点。总结来说，对于任意一个数字n，它都会存在n*10+0到n*10+9这10个子节点。

构建好字典十叉树之后，将字典树按照字典顺序输出实际上就是对树进行前序遍历，我们之前文章已经多次讲到过，对树形结构进行遍历的最好方式就是dfs深度优先搜索，dfs的起点有9个数字，分别是1-9，dfs的终止条件为当前点数字大于给定的数字n。

实现代码：

List<Integer> res=new ArrayList<>(); // 返回结果
public List<Integer> lexicalOrder(int n) {
    // 分别以1-9作为起点开始dfs前序遍历十叉树，
    for(int i=1;i<=9;i++){
        help(i, n);
    }
    return res;
}

void help(int num, int max){
    // 如果当前数字大于max，返回
    if(num>max) return;
    // 将当前数字加入返回结果
    res.add(num);
    // 将当前数字乘以10
    num*=10;
    // 如果大于max，返回
    if(num>max) return;
    // 循环dfs当前数字的10个子节点
    for(int i=0;i<=9;i++){
        help(num+i,max);
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Lexicographical Numbers.

Memory Usage: 45.8 MB, less than 6.67% of Java online submissions for Lexicographical Numbers.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-386-lexicographical-numbers-解题思路分析/