0386. Lexicographical Numbers¶
题目信息¶
- 题号:
0386
- 难度:
Medium
- 主题:
整数范围、十进制字典序、完整输出、复杂度要求
- 原题:
- 重点:
返回 1 到 n 的全部整数、比较依据是十进制文本字典序、要求线性时间和常数级辅助空间
题目重述¶
给定正整数 n,返回闭区间 [1, n] 中的全部整数,并按照它们不带前导零的十进制表示进行字典序排列。例如在字典序中,前缀 1 后面先出现 10、100 等,再轮到 2。
n 位于 [1, 5 * 10^4]。结果必须恰好包含每个整数一次。题目要求总时间复杂度为 O(n),除返回数组外只使用常数级额外空间;不能通过把全部整数转为字符串后整体排序来绕开该要求。
自建示例¶
两位数进入前缀顺序:
输入:n = 12
输出:[1,10,11,12,2,3,4,5,6,7,8,9]
解释:按十进制字符串比较时,"10"、"11"、"12" 都以 "1" 开头,因此排在 "2" 之前。
范围只有两个整数:
输入:n = 2
输出:[1,2]
解释:结果包含区间内每个整数一次,二者字典序与数值顺序相同。
把十进制前缀当作一棵树¶
数字的字典序遍历可以看成前缀树的先序遍历:从 1 开始,若当前数乘 10 仍不超过 n,就进入它的下一位子节点;否则说明当前分支已经走到底,沿父节点回退,直到可以把当前前缀加 1。回退时跳过末位为 9 或已经超过 n 的前缀。
该过程直接在整数前缀上移动,不建立字符串,也不使用额外的访问集合;每个整数输出一次,回退和扩展的总移动次数与输出规模同阶。
C++ 实现¶
class Solution {
public:
std::vector<int> lexicalOrder(int n) {
std::vector<int> result;
result.reserve(n);
long long current = 1;
for (int i = 0; i < n; ++i) {
result.push_back(static_cast<int>(current));
if (current * 10 <= n) {
current *= 10;
} else {
while (current % 10 == 9 || current + 1 > n) {
current /= 10;
}
++current;
}
}
return result;
}
};
代码分析¶
乘 10 相当于进入当前前缀的最小子树,除以 10 相当于回到父前缀;current 使用宽类型避免中间乘 10 溢出。除返回数组外只使用常数级状态,输出本身占 O(n),总遍历时间为 O(n)。