题意整理

  • 给定一个用数组表示的数字,即数组中每个数表示一个数位上的数,例如[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的时候,才需要重新定义新数组,大多数情况下会直接返回原数组。空间开销和时间开销都有所减小。

图解展示: alt

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)