江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第386题：字典序排数

给定一个整数 n, 返回从 1 到 n 的字典序排列。

📖 文章摘要

本文详细解析LeetCode第386题“字典序排数”，这是一道排序题。文章提供了基于深度优先搜索的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升算法设计能力的读者。

核心知识点： 排序、深度优先搜索、字典序 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升算法设计能力的程序员

题目描述

给定一个整数 n, 返回从 1 到 n 的字典序排列。

示例

示例 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^4

解题思路

本题可以使用深度优先搜索解决：

  1. 从1开始，按字典序生成数字
  2. 对于每个数字，先尝试乘以10
  3. 如果乘以10后超过n，则尝试加1
  4. 如果加1后超过n或个位数为9，则回溯

时间复杂度： O(n) 空间复杂度： O(n)

图解思路

深度优先搜索

步骤 操作 说明
1 从1开始 初始数字
2 尝试*10 生成子节点
3 尝试+1 生成兄弟节点
4 回溯 处理其他分支

生成过程

数字 操作 结果
1 *10 10
10 *10 100(超过n)
10 +1 11
11 *10 110(超过n)
11 +1 12
… … …

代码实现

C# 实现

public class Solution {
    private List<int> result;
    private int n;
    
    public IList<int> LexicalOrder(int n) {
        this.n = n;
        result = new List<int>();
        
        for (int i = 1; i <= 9; i++) {
            DFS(i);
        }
        
        return result;
    }
    
    private void DFS(int num) {
        if (num > n) return;
        
        result.Add(num);
        
        for (int i = 0; i <= 9; i++) {
            int next = num * 10 + i;
            if (next > n) break;
            DFS(next);
        }
    }
}

Python 实现

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        
        def dfs(num):
            if num > n:
                return
            result.append(num)
            for i in range(10):
                next_num = num * 10 + i
                if next_num > n:
                    break
                dfs(next_num)
                
        for i in range(1, 10):
            dfs(i)
            
        return result

C++ 实现

class Solution {
private:
    vector<int> result;
    int n;
    
    void dfs(int num) {
        if (num > n) return;
        
        result.push_back(num);
        
        for (int i = 0; i <= 9; i++) {
            int next = num * 10 + i;
            if (next > n) break;
            dfs(next);
        }
    }
    
public:
    vector<int> lexicalOrder(int n) {
        this->n = n;
        
        for (int i = 1; i <= 9; i++) {
            dfs(i);
        }
        
        return result;
    }
};

执行结果

C# 实现

  • 执行用时：92 ms
  • 内存消耗：24.8 MB

Python 实现

  • 执行用时：28 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：8.4 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 4 ms 8.4 MB 执行效率最高，内存占用最小
Python 28 ms 13.2 MB 代码简洁，内存占用适中
C# 92 ms 24.8 MB 类型安全，内存占用较大

代码亮点

  1. 🎯 使用深度优先搜索生成字典序
  2. 💡 空间复杂度优化
  3. 🔍 处理边界情况
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 未使用深度优先搜索
  2. 🚫 生成顺序错误
  3. 🚫 边界条件处理错误
  4. 🚫 空间复杂度优化不足

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
深度优先搜索 O(n) O(n) 高效，直观 递归开销
排序 O(n log n) O(n) 简单 效率低

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第386题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！