What is the key pattern for solving Lexicographical Numbers?

The problem uses a depth-first search pattern combined with trie-like prefix expansion to generate numbers lexicographically.

Can this be solved without recursion?

Yes, iterative traversal multiplying by 10 and adjusting numbers simulates the DFS-trie pattern without recursion, preserving O(1) space.

Why can't we just sort numbers from 1 to n?

Sorting adds O(n log n) time and extra space, whereas DFS-trie traversal achieves O(n) time and minimal space.

What are common mistakes in this problem?

Exceeding n during recursion, forgetting to handle trailing zeros, or using extra arrays for prefixes are typical pitfalls.

Does this pattern work for very large n, like 50000?

Yes, following the DFS-trie approach carefully ensures O(n) traversal with O(1) extra space, suitable even for the upper constraint.

#386

Medium

auto_awesome图·搜索

LeetCode 题解工作台

字典序排数

给你一个整数 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] 提…

深度优先搜索字典树

题目描述

给你一个整数 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 * 10⁴

lightbulb

解题思路

方法一：迭代

我们首先定义一个变量 $v$ ，初始时 $v = 1$ 。然后我们从 $1$ 开始迭代，每次迭代都将 $v$ 添加到答案数组中。然后，如果 $v \times 10 \leq n$ ，我们将 $v$ 更新为 $v \times 10$ ；否则，如果 $v \bmod 10 = 9$ 或者 $v + 1 > n$ ，我们就循环将 $v$ 除以 $10$ 。循环结束后，我们将 $v$ 加一。继续迭代，直到我们添加了 $n$ 个数到答案数组中。

时间复杂度 $O(n)$ ，其中 $n$ 是给定的整数 $n$ 。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans = []
        v = 1
        for _ in range(n):
            ans.append(v)
            if v * 10 <= n:
                v *= 10
            else:
                while v % 10 == 9 or v + 1 > n:
                    v //= 10
                v += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) because each number from 1 to n is visited exactly once during DFS traversal. Space complexity is O(1) beyond the output list since only a single integer is tracked during iteration or recursion, avoiding extra data structures.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Asks how to generate numbers without sorting the final list.
question_mark
Checks understanding of DFS traversal applied to number prefixes.
question_mark
Tests ability to optimize space usage for large n values.

warning

常见陷阱

外企场景

error
Forgetting to stop recursion when the number exceeds n.
error
Using built-in sort instead of generating numbers lexicographically.
error
Exceeding space limits by storing unnecessary intermediate data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate numbers in reverse lexicographical order using the same DFS-trie pattern.
arrow_right_alt
Limit the output to numbers containing a specific digit while maintaining lexicographical order.
arrow_right_alt
Adapt the approach for a range [m, n] instead of starting from 1, adjusting prefix exploration accordingly.

help

常见问题

外企场景

继续练习

#472 连接词 #211 添加与搜索单词 - 数据结构设计 #676 实现一个魔法字典