386. 字典序排数

🟠   🔖  深度优先搜索 字典树  🔗 力扣 LeetCode

题目

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1:

Input: n = 13

Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2

Output: [1,2]

Constraints:

• 1 <= n <= 5 * 10^4

题目大意

给你一个整数 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 倍。
   • 如果扩大 10 倍超出范围，则考虑“进位”操作（即调整末位的递增）。

2. 处理特殊情况

   • 当当前数 num * 10 <= n 时，将数变为其十倍（如从 1 变到 10）。
   • 当数末尾为 9 或者已经超出范围，则需要缩小数值并增加到下一个字典序位置。

复杂度分析

• 时间复杂度: O(n)，每个整数被访问一次，总共有 n 个数。
• 空间复杂度: O(1)，除结果数组外，仅使用常数空间。

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function (n) {
	let res = [];
	let num = 1;
	while (res.length < n) {
		res.push(num);
		if (num * 10 <= n) {
			num *= 10;
		} else {
			while (num % 10 == 9 || num >= n) {
				num = Math.floor(num / 10);
			}
			num++;
		}
	}
	return res;
};