LeetCode题练习与总结：字典序排数--386

一、题目描述

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

二、解题思路

我们可以从1开始，每次找到当前数字的下一个字典序的数字。例如，如果当前数字是1，那么下一个字典序的数字是10，而不是2。
我们可以通过在当前数字后面添加一个0来找到下一个字典序的数字。但是，如果添加0后的数字大于n，我们需要回退到上一个数字，然后增加1，再重复这个过程。
当我们找到一个数字，如果它小于等于n，我们就将其添加到结果列表中，然后继续寻找下一个字典序的数字。
我们重复这个过程，直到我们找到的所有数字都大于n。

三、具体代码

import java.util.ArrayList;
import java.util.List;class Solution {public List<Integer> lexicalOrder(int n) {List<Integer> result = new ArrayList<>();int current = 1;for (int i = 1; i <= n; i++) {result.add(current);if (current * 10 <= n) {current *= 10;} else {while (current % 10 == 9 || current + 1 > n) {current /= 10;}current++;}}return result;}
}

解释：

我们初始化current为1，并将其添加到结果列表中。
在每次循环中，我们检查current * 10是否小于等于n。如果是，我们将current乘以10，以找到下一个字典序的数字。
如果current * 10大于n，我们需要找到下一个数字。我们通过不断除以10来跳过以9结尾的数字，或者当current + 1大于n时停止。
最后，我们将current加1，以找到下一个字典序的数字，并继续循环直到找到所有数字。

四、时间复杂度和空间复杂度

1. 时间复杂度

循环次数：代码中有一个for循环，循环次数为n（即输入的整数n）。
循环体内的操作：每次循环中，我们添加一个数字到结果列表，这个操作是常数时间复杂度O(1)。接下来，我们可能需要对current进行多次除以10的操作，直到找到下一个合适的数字。在最坏的情况下，current需要除以10的次数最多为数字的位数，由于n的最大值为5 * 10^4，所以current的位数最多为6位（即最大为59999），这意味着除以10的操作最多执行6次，这是一个常数。
综合考虑：由于每次循环中的操作都是常数时间复杂度，并且循环次数为n，所以总的时间复杂度为O(n)。

2. 空间复杂度

结果列表：我们创建了一个列表来存储结果，列表的大小为n，因此需要O(n)的空间。
其他变量：除了结果列表之外，我们只使用了几个整数变量（如current和循环变量i），这些变量占用常数空间O(1)。
综合考虑：虽然我们使用了O(n)的空间来存储结果，但是题目要求不包括返回结果所需的空间。因此，除了返回结果所需的空间之外，算法使用的额外空间为O(1)。

五、总结知识点

Java 类定义：
- class 关键字用于定义一个类。
- 类名通常首字母大写，这里是 Solution。
成员方法：
- public 关键字表示方法的访问权限，允许其他类访问。
- List<Integer> 表示方法返回一个整数列表。
- 方法名为 lexicalOrder，接收一个整数参数 n。
Java 集合框架：
- List 接口用于表示有序集合。
- ArrayList 类实现了 List 接口，用于创建动态数组。
循环控制：
- for 循环用于重复执行代码块，直到给定的条件不再满足。
- 循环变量 i 用于跟踪循环的次数。
条件语句：
- if-else 语句用于根据条件执行不同的代码块。
- while 循环用于在给定条件为真时重复执行代码块。
算术运算：
- * 表示乘法运算。
- / 表示除法运算。
- % 表示取模运算，用于判断一个数是否能被另一个数整除。
赋值运算：
- = 用于赋值。
- ++ 用于自增操作。
逻辑运算符：
- || 表示逻辑或运算。
- && 表示逻辑与运算。
方法调用：
- add 方法用于向列表中添加元素。
返回语句：
- return 关键字用于从方法中返回值。