leetcode
leetcode 351 ~ 400
字典序排数

字典序排数

难度:

标签:

题目描述

给你一个整数 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在这个问题中更为合适,因为它可以更自然地按字典序生成数字。使用DFS时,我们可以从一个数开始,深入到它的所有可能的后续数字(如从1深入到10,100等),这恰好符合字典序排列的需求。相比之下,BFS会同时处理同一层级的所有数字,需要额外的存储空间来维护这一层的所有元素,这与题目要求的O(1)额外空间不符。
🦆
在递归函数`dfs`中,如何保证生成的数字不超过给定的整数`n`?
在`dfs`函数中,每次递归生成新数字前,都会检查这个数字是否小于等于`n`。这通过条件`min(n + 1, (x + 1) * 10)`实现,它确保不会生成超过`n`的数字。此外,每次生成的下一个数字都是当前数字的10倍或在此基础上加上一个[0-9]的数,这样的递归保证了只有满足条件的数字才会被进一步探索。
🦆
在生成数字的过程中,为何使用`min(n + 1, (x + 1) * 10)`来确定下一个数字的范围?
这个表达式用来确定下一个可能的数字范围以避免超出`n`。`(x + 1) * 10`表示下一个可能的十倍数节点(例如从1到10),而`n + 1`是因为我们需要包括`n`本身(如果`n`是个十倍数)。使用`min`函数确保即使计算的下一个节点起始值超过了`n`,也只会生成到`n`为止的数字,从而避免超出范围的生成,确保了程序的健壮性和正确性。

相关问题