文章目录
题目
给你一个整数 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]
提示：
1 <= n <= 5 * 104
答案
1、暴力法
import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * @Author: Ljx * @Date: 2022/4/18 17:15 * @role: https://leetcode-cn.com/problems/lexicographical-numbers/ */ public class 字典序排数 { public static void main(String[] args) { System.out.println(lexicalOrder(13)); } public static List<Integer> lexicalOrder(int n) { List<String> strings = new ArrayList<>(); for (int i = 1; i <= n; i++) { strings.add(String.valueOf(i)); } Collections.sort(strings); List<Integer> list = new ArrayList<>(); for (String string : strings) { list.add(Integer.valueOf(string)); } return list; } }
2、递归
public class 字典序排数 { public static void main(String[] args) { System.out.println(lexicalOrder(13)); } public static List<Integer> lexicalOrder(int n) { List<Integer> ans=new ArrayList<>(); addNum(0,n,ans); return ans; } public static void addNum(int k,int n,List<Integer> ans){ if(k>n){ return; } if(k>0){ ans.add(k); } k *= 10; for(int i=k==0?1:0;i<10;i++){ addNum(k+i,n,ans); } } }
3、官方答案
深度优先搜索
思路与算法
题目要求设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法，因此我们不能使用直接排序的方法。
那么对于一个整数 number，它的下一个字典序整数对应下面的规则：
尝试在 number 后面附加一个零，即 number×10，如果 number×10≤n，那么说明 number×10 是下一个字典序整数；
如果 number mod 10=9 或 number + 1 >n，那么说明末尾的数位已经搜索完成，退回上一位，即 number=[number/10]，然后继续判断直到 number mod 10 !=9 且 nnumber+1≤n 为止，那么 number+1 是下一个字典序整数。
字典序最小的整数为number=1，我们从它开始，然后依次获取下一个字典序整数，加入结果中，结束条件为已经获取到 n 个整数。
class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> ret = new ArrayList<Integer>(); int number = 1; for (int i = 0; i < n; i++) { ret.add(number); if (number * 10 <= n) { number *= 10; } else { while (number % 10 == 9 || number + 1 > n) { number /= 10; } number++; } } return ret; } }
