字典序排数
难度:
标签:
题目描述
给你一个整数 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
代码结果
运行时间: 24 ms, 内存: 22.7 MB
/*
* 题目思路:
* 给定一个整数 n,要求返回从 1 到 n 的所有整数按字典序排序后的结果。
* 使用 Java Stream API 来实现该功能。
*/
import java.util.*;
import java.util.stream.*;
public class LexicographicalNumbersStream {
public List<Integer> lexicalOrder(int n) {
return IntStream.rangeClosed(1, n)
.boxed()
.sorted((a, b) -> String.valueOf(a).compareTo(String.valueOf(b)))
.collect(Collectors.toList());
}
public static void main(String[] args) {
LexicographicalNumbersStream ln = new LexicographicalNumbersStream();
System.out.println(ln.lexicalOrder(13)); // [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
解释
方法:
解题思路是使用深度优先搜索(DFS)来按字典序生成数字。从1到9开始,每个数字可以视为树的根节点,然后对于每个节点x,其子节点可以是x*10, x*10+1, ..., x*10+9,前提是这些子节点必须小于等于n。通过递归地生成每个数字的所有可能的子数字,我们可以构建出一个按字典序排列的数字列表。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择深度优先搜索(DFS)而不是广度优先搜索(BFS)或其他方法来解决这个问题?
▷🦆
在递归函数`dfs`中,如何保证生成的数字不超过给定的整数`n`?
▷🦆
在生成数字的过程中,为何使用`min(n + 1, (x + 1) * 10)`来确定下一个数字的范围?
▷