数组-构建并打印数组

十二月 22, 2021 2477

        每日一题，提升自己。今天分享一道关于构建并打印数组的题目，且听我细细道来。

数组 - 构建并打印数组

1. 题目描述

        输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例：

输入：n=1

输出：[1,2,3,4,5,6,7,8,9]

提示：

  1. 用返回一个整数列表来代替打印。
  2. n 为正整数。

2. 解题思路

2.1 思路一

        首先根据输入的数字求出要打印的范围，然后再从1开始打印到最大的数字。

复杂度：

  • 时间复杂度：O(10^n)。
  • 空间复杂度：O(10^n)。

2.2 思路二

本题的题意是希望考察大数的计算，因为int数组有可能会有益出，所以用字符串可以保证一定不会溢出。但是呢，由于规定的返回值是int数组，所以其实从返回值上来看，是一定不会溢出的，比较矛盾。这里给出思路二只是学习一下如何用字符串处理大数即可，不用特别纠结溢出这件事上。和思路一一样，先求出数字范围，然后从1开始打印到最大的数字，只不过这里用的是字符串去处理。

  • 时间复杂度：O(10^n)。
  • 空间复杂度：O(10^n)。

3. 算法流程

3.1 思路一流程

  1. 初始化sum=1。
  2. 循环遍历乘10，让sum变为边界值。
  3. 新建res数组，长度大小为sum-1。
  4. 从1开始存入res，知道sum-1。

3.2 思路二流程

  1. 初始化返回数组res，长度为最大值减一。
  2. 初始化字符串sb，使其初始值为n个”0”。
  3. 递增sb，使用字符去递增，递增过程中需要判断是否进位，存在进位则进位出加一，直到达到最大值为止，结束循环。
  4. 每次获取到一个值之后，遍历前方多余的”0”，将多余的”0”去掉，然后转换为int存到结果数组中。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
public static int[] printNumbers(int n){
    int sum = 1;
    for (int i=0;i<n;i++){
        sum *= 10;
    }
    int[] res = new int[sum - 1];
    for (int i=0; i<sum-1; i++){
        res[i] = i + 1;
    }
    return res;
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static int[] printNumbers_2(int n){
    int[] res = new int[(int)Math.pow(10,n) - 1];
    StringBuilder sb = new StringBuilder();
    // 初始化字符串为n个"0"
    for (int i=0; i<n; i++){
        sb.append('0');
    }
    int count = 0;
    while (!increment(sb)){
        int index = 0;
        while (index<sb.length() && sb.charAt(index)=='0'){
            index++;
        }
        // 从当前位置开始截取到最后，作为目标数存入
        res[count] = Integer.parseInt(sb.toString().substring(index));
        count++;
    }
    return res;
}

// 数字字符串加一的操作
public static boolean increment(StringBuilder sb){
    boolean isCarry = false;
    for (int i=sb.length()-1; i>=0; i--){
        // 数字字符+1
        char s = (char) (sb.charAt(i)+1);
        // 判断是否进位
        if (s>'9'){
            // 进位则当前位置到最后替换成0
            sb.replace(i,i+1,"0");
            // 当前是否是第0个，是就不能进位
            if (i == 0){
                isCarry = true;
            }
        }else {
            // 如果不进位，则当前位置到最后替换成加一后的字符
            sb.replace(i,i+1,String.valueOf(s));
            break;
        }

    }
    return isCarry;
}