题解 | #给数组加一#

给数组加一

题目描述

给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如 [1,2,3]，表示 123 ，请问给这个数字加一后得到的结果（结果同样以数组的形式返回）。

注意：数组中不可能出现负数，且保证数组的首位即数字的首位不可能是 0 。

方法一：直接法

解题思路

对数组进行逆序遍历，模拟加一操作，此时需要一个辅助数组来存储结果。

解题代码

class Solution {
public:
    
    vector<int> plusOne(vector<int>& nums) {
        vector<int> res;
        int flag=1;//进位
        for(int i=nums.size()-1;i>=0;i--)
        {//逆向遍历
            res.push_back((nums[i]+flag)%10);
            if(nums[i]+flag>9)
            {//判断进位
                flag=1;
            }
            else
            {
                flag=0;
            }
        }
        if(flag)
        {//判断进位
            res.push_back(1);
        }
        reverse(res.begin(),res.end());//逆序
        return res;// 返回结果
    }
};

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：不使用辅助数组的方法

解题思路

基于方法一，不借助辅助数组来对原数组进行加法操作，此时需要逆序，判断进位以后再逆序。

解题代码

class Solution {
public:
    
    vector<int> plusOne(vector<int>& nums)
    {
        int flag=1;//进位
        for(int i=nums.size()-1;i>=0;i--)
        {//逆向遍历
            if(nums[i]+flag>9)
            {//判断进位
                nums[i]=(nums[i]+flag)%10;
                flag=1;
            }
            else
            {
                nums[i]=(nums[i]+flag)%10;
                flag=0;
            }
        }
        reverse(nums.begin(),nums.end());//逆序
        if(flag)
        {//判断进位
            nums.push_back(1);
        }
        reverse(nums.begin(),nums.end());//逆序
        return nums; // 返回结果
    }
};

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$