X

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-解题思路分析/
Categories: leetcode
kwantong: