题解 | #给数组加一#

题意整理

• 给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如$[1,2,3][1,2,3]$，表示123。
• 求这个数字加1后的结果，以数组的形式返回。

方法一（模拟）

1.解题思路

• 首先定义一个长度为n+1的新数组res和一个进位carry。
• 然后逆序遍历原数组，根据进位，模拟数组加1的过程。
• 如果最后进位为0，说明数组长度不变，只需返回res最后n位。如果进位位1，则需要给索引位0的位置赋值，并返回新数组。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] plusOne (int[] nums) {
        int n=nums.length;
        //定义一个长度为n+1的新数组
        int[] res=new int[n+1];
        //进位
        int carry=1;
        for(int i=n-1;i>=0;i--){
            //给新数组赋值
            res[i+1]=(nums[i]+carry)%10;
            if(nums[i]+carry>9){
                carry=1;
            }
            else{
                carry=0;
            }
        }
        //如果最后进位为0，说明数组长度不变，只需返回最后n位
        if(carry==0){
            return Arrays.copyOfRange(res,1,n+1);
        }
        else{
            //如果进位位1，则需要给索引位0的位置赋值
            res[0]=1;
            //直接返回res
            return res;
        }
    }
}

3.复杂度分析

• 时间复杂度：需要遍历原数组一遍，时间复杂度为$O(n)O(n)$，如果最后进位为0，还需要复制新数组的最后n位，时间复杂度也为$O(n)O(n)$，所以最终的时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间（没有算返回数组的空间开销），所以空间复杂度为$O(1)O(1)$。

方法二（原地操作）

1.解题思路

• 逆序遍历原数组。
• 如果不为9，说明之后的位进位全为0，直接在当前位加上1，并返回nums。否则，对应位变为0。
• 如果遍历完之后，没有返回原数组，则定义一个新数组，开始位置设为1，然后直接返回。

与方法一比较，只需要遍历数组一次，而且最后进位为1的时候，才需要重新定义新数组，大多数情况下会直接返回原数组。空间开销和时间开销都有所减小。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] plusOne (int[] nums) {
        int n=nums.length;
        for(int i=n-1;i>=0;i--){
            //如果不为9，直接对应位加上1，并返回nums
            if(nums[i]!=9){
                nums[i]=nums[i]+1;
                return nums;
            }
            //否则，对应位变为0
            else{
                nums[i]=0;
            }
        }
        //定义一个新数组
        int[] res=new int[n+1];
        //开始位置设为1，然后直接返回
        res[0]=1;
        return res;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历原数组一遍，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间（没有算返回数组的空间开销），所以空间复杂度为$O(1)O(1)$。