LeetCode 剑指 Offer 17. 打印从1到最大的n位数
题目描述
题意分析
按数值从小到大的顺序列出从
1到最大n位十进制正整数的所有数字。最大的n位数是10^n - 1，因此共有10^n - 1个结果，不包含零，也不能只输出恰好有n位的数字。这里有两种输出约定：在线题的整数数组接口需要返回全部结果；上方原书题面要求按顺序打印，没有给出可直接用小整数保存的位数上限。数组接口可以在整数与内存能承载的范围内顺序填充；若要处理超过固定整数范围的数，则应使用字符表示每一位，并逐项输出，不能再把大数转回
int。大数表示解决的是单个数字溢出，逐项输出避免保存全部结果，但都不能改变结果数量为指数级这一事实。位数很大时，完整打印所需的时间仍然很长。
解法：整数上界 + 顺序填充
核心思路
[!blue]
对于返回整数数组的版本，输出范围已经完全确定，不需要搜索或排序。先从一开始连续乘十
n次，得到不包含在结果中的上界limit = 10^n，最后要输出的数就是limit - 1。从一到
limit - 1一共有limit - 1个数字，所以结果数组长度也是这个值。数组下标从零开始，而输出数值从一开始，将下标i写成i + 1，就能让每个需要的数字恰好出现一次，并且自然按升序排列。整数连乘避免了浮点幂运算与类型转换，但没有消除整数容量和数组大小限制。下面保留原整数返回接口，它适用于上界与完整数组都可承载的输入；不限数字大小的打印要求由后面的字符数组方法处理。
这类题无法通过更复杂的算法省掉输出本身：既然接口要求显式返回每个数字，就至少需要写入同样数量的数组元素。
解题步骤
- 初始化
limit = 1，连续乘十n次，得到第一个超出输出范围的数。- 分配长度为
limit - 1的整数数组。- 遍历数组下标
i，将当前位置写成i + 1。- 返回数组，最后一项恰好是
10^n - 1。
代码实现
class Solution {
public int[] printNumbers(int n) {
int limit = 1;
for (int i = 0; i < n; i++) {
limit *= 10;
}
// 最大输出为十的 n 次方减一，结果数量与最大值相同
int[] result = new int[limit - 1];
for (int i = 0; i < result.length; i++) {
// 数组下标从零开始，输出数字从一开始
result[i] = i + 1;
}
return result;
}
}
func printNumbers(n int) []int {
limit := 1
for i := 0; i < n; i++ {
limit *= 10
}
// 最大输出为十的 n 次方减一，结果数量与最大值相同
result := make([]int, limit-1)
for i := range result {
// 数组下标从零开始，输出数字从一开始
result[i] = i + 1
}
return result
}
复杂度分析
- 时间复杂度：
O(10^n)。计算上界需要O(n)，写入10^n - 1个结果决定总开销。- 空间复杂度：返回数组占
O(10^n)；除返回结果外只使用常数个变量，辅助空间为O(1)。
关键点总结
[!green]
- 上界
10^n本身不输出，最大值和结果数量都是10^n - 1。- 下标到数值的固定偏移保证不重不漏，数组无需排序。
- 整数数组接口与不限数字大小的逐项打印是不同的约定，应分别说明适用范围。
补充解法：字符数组模拟大数加一
核心思路
[!blue]
用长度为
n的字符数组保存十进制数，高位在前、低位在后，初始每一位都是零。数组长度只与位数有关，不需要把整个数放进一个整数变量，因此不会因为数值超过int或long而溢出。每轮先模拟加一。从最右边开始，遇到九就把这一位改为零，继续向左进位；遇到不是九的一位，就把它加一，进位结束。这与十进制加法完全一致，所以每轮恰好得到前一个数的后继，按顺序覆盖所有正整数而不重复。
如果进位越过了最左边，说明之前已经输出过全为九的最大值，此时直接结束。其余情况下加一后的数必然非零，从左到右跳过前导零，将剩余有效部分作为字符串输出。初始的全零数组不输出，因而结果自然从一开始。
下面的
output每次接收一个不带前导零的数字字符串，由调用方打印或处理，不需要把所有结果保存起来。数组始终复用，但交出的字符串是当前数字的一份独立结果，不会被后面的加一覆盖。
解题步骤
n <= 0时没有要打印的正整数，直接返回；否则创建n位全零字符数组。- 从末位向左处理进位，将连续的九归零。
- 如果全部位都产生了进位，结束；否则把第一个非九的数位加一。
- 找到第一个非零位，生成从该位置到末尾的字符串，并交给
output。- 重复模拟加一，直到越过最大
n位数。
代码实现
class Solution {
public void printNumbersAsStrings(int n, java.util.function.Consumer<String> output) {
if (n <= 0) {
return;
}
char[] digits = new char[n];
java.util.Arrays.fill(digits, '0');
while (true) {
int position = n - 1;
while (position >= 0 && digits[position] == '9') {
digits[position] = '0';
position--;
}
if (position < 0) {
return;
}
digits[position]++;
int first = 0;
while (digits[first] == '0') {
first++;
}
output.accept(new String(digits, first, n - first));
}
}
}
func printNumbersAsStrings(n int, output func(string)) {
if n <= 0 {
return
}
digits := make([]byte, n)
for i := range digits {
digits[i] = '0'
}
for {
position := n - 1
for position >= 0 && digits[position] == '9' {
digits[position] = '0'
position--
}
if position < 0 {
return
}
digits[position]++
first := 0
for digits[first] == '0' {
first++
}
output(string(digits[first:]))
}
}
复杂度分析
- 时间复杂度：
O(n × 10^n)。共生成10^n - 1个数，每次加一、查找有效起点和构造输出字符串最多处理n位；逐项打印完整数字也需要写出这些字符。- 空间复杂度：
O(n)。保存一个n位字符数组和当前输出字符串，不计调用方主动保留输出所用的空间。
关键点总结
[!green]
- 数位数组模拟加一，不通过整数变量存放整个数值。
- 先加一再输出，自动跳过零；最高位进位作为唯一结束标志。
- 输出时去掉前导零，内部仍保留固定长度，便于连续进位。
- 逐项输出节省的是存储全部结果的空间，输出总量仍随位数指数增长。
易错点总结
[!yellow]
- 从零开始输出或只输出
n位数字：正确范围包含所有一位到n位的正整数，起点是一。- 把
10^n也加入结果：这个数已经有n + 1位，不属于输出范围。- 认为使用整数连乘就不会溢出：连乘仍受整数类型限制，大数题型应直接维护十进制字符。
- 把字符数组再解析成整数输出：会重新引入已经避开的整数范围限制，应直接输出字符串。
- 字符加一结束后输出全零数组：最高位进位表示已经处理完最大
n位数，应立即结束。- 把全部大数字符串收集进列表：会重新需要指数级返回空间，逐项输出版本应在生成后直接交给调用方处理。