给数组加一

题意

给定一个数组表示的数字，对这个数字加1，同样返回数组表示的数字

方法

python内置高精度

分析

直接把数字数组转换成数字，然后数字+1，最后把数字转换回数组

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def plusOne(self , nums: List[int]) -> List[int]:
        v = 0
        for d in nums:
            v*=10
            v+=d
        v += 1
        r = []
        while v:
            r = [v%10] + r
            v //= 10
        return r

复杂度分析

空间复杂度: 主要是结果返回，所以空间复杂度为$O(n)O(n)$

时间复杂度: 对于每个位置的操作是常数代价，所以总时间复杂度为$O(n)O(n)$

模拟加法

分析

如果全是9，及999...999, 那么加1后就是1000...000 比原来多1位，特殊处理

如果不全是9, 那么加1后不会进位

从低位到高位，模拟加法，遇到9则进位，非9则加1返回

样例

以样例数据为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> plusOne(vector<int>& nums) {
        int all9 = true; // 全是9
        for(auto v:nums){
            if(v != 9){ // 存在不是9的
                all9 = false;
                break;
            }
        }
        if(all9){
            vector<int> ans = vector<int>(nums.size()+1,0); // 直接返回
            ans[0] = 1;
            return ans;
        }
        for(int i = nums.size()-1;i>=0;i--){ // 从低位到高位
            if(nums[i] == 9){ // 进位
                nums[i] = 0;
            }else{
                nums[i]++; // 加一返回
                return nums;
            }
        }
        assert(false); // 不会到达
        return {};
    }
};

复杂度分析

时间复杂度: 枚举了每个位置，每个位置操作为常数代价，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 用的额外空间和原数组大小相当，所以空间复杂度为$O(n)O(n)$