一、题目

1、题目描述

  输入数字 n n n，按顺序打印出从 1 1 1 到最大的 n n n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
  样例输入： n = 1
  样例输出： [1,2,3,4,5,6,7,8,9]

2、基础框架

• C语言 版本给出的基础框架代码如下：

int* printNumbers(int n, int* returnSize){ }

3、原题链接

剑指 Offer 17. 打印从1到最大的n位数

二、解题报告

1、思路分析

  通过遍历，不断乘 10 10 10，乘了 n n n 次，得到的就是 10 10 10 的 n n n 次方。 1 0 n − 1 10^n-1 10n−1 就是 n n n 位数的最大值了，剩下的就是从 1 开始遍历到这个最大值的过程了。

2、时间复杂度

  时间复杂度为 O ( 1 0 n ) O(10^n) O(10n)。

3、代码详解

int* printNumbers(int n, int* returnSize){
    int i;
    int f = 1;
    int *ret;

    for(i = 0; i < n; ++i) {
        f *= 10;                               // (1)
    }
    --f;
    *returnSize = f;
    ret = (int *)malloc( f * sizeof(int) );
    for(i = 1; i <= f; ++i) {
        ret[i-1] = i;                          // (2)
    }
    return ret;
}

• ( 1 ) (1) (1) 计算 1 0 n 10^n 10n 的过程。
• ( 2 ) (2) (2) 遍历 [ 1 , 1 0 n − 1 ] [1, 10^n-1] [1,10n−1]， 存储到数组中。

三、本题小知识

通过遍历，不断乘 10 10 10，乘了 n n n 次，得到的就是 10 10 10 的 n n n 次方。

四、加群须知

  相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
  那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：