LeetCode 0386.字典序排数：细心总结条件

【LetMeFly】386.字典序排数：细心总结条件

力扣题目链接：https://leetcode.cn/problems/lexicographical-numbers/

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

解题方法：if-else

解题思路

使用O(1)的空间和O(n)的时间完成本题，不如先想想字典序下到底是个什么顺序。

1. 首先是1、10、100、…，直到即将大于n为止（假设n=200，那么100即将大于n(100*10=1000)）
2. 100后接着是101、102、…109
3. 109之后是11（而不是110），之后进入第一步(11、110、…)

基本上就这三种情况。

具体做法

使用一个变量now记录当前的值，如果$now\times 10\le n$就让$now\times 10$，否则：

就让$now+1$。特别的，在$now+1$之前，若$now$的最后一位已经是$9$或者$now$已经等于了$n$，就不断移除$now$的最后一位(109变成10)。

时空复杂度分析

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-06-09 10:09:21* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-09 10:15:25*/
class Solution {
public:vector<int> lexicalOrder(int n) {vector<int> ans(n);int now = 1;for (int i = 0; i < n; i++) {ans[i] = now;if (now * 10 <= n) {now *= 10;} else {while (now % 10 == 9 || now == n) {now /= 10;}now++;}}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-06-09 10:09:21
LastEditors: LetMeFly.xyz
LastEditTime: 2025-06-09 10:21:53
'''
from typing import Listclass Solution:def lexicalOrder(self, n: int) -> List[int]:ans = [0] * nnow = 1for i in range(n):ans[i] = nowif now * 10 <= n:now *= 10else:while now % 10 == 9 or now == n:now //= 10now += 1return ans

Java

/** @Author: LetMeFly* @Date: 2025-06-09 10:09:21* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-09 22:00:48*/
import java.util.List;
import java.util.ArrayList;class Solution {public List<Integer> lexicalOrder(int n) {List<Integer> ans = new ArrayList<>();for (int now = 1, i = 0; i < n; i++) {ans.add(now);if (now * 10 <= n) {now *= 10;} else {while (now % 10 == 9 || now == n) {now /= 10;}now++;}}return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-06-09 10:09:21* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-06-09 22:03:40*/
package mainfunc lexicalOrder(n int) []int {ans := make([]int, n)for now, i := 1, 0; i < n; i++ {ans[i] = nowif now * 10 <= n {now *= 10} else {for now % 10 == 9 || now == n {now /= 10}now++}}return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源