题目大意:
字典序排数
给定一个整数 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-解题思路分析/