描述

使用一个整型数组表示一个整数，写一个函数给这个整数加1.

分析

数组表示一个整数，在进行加法运算时需要从数组尾部向头部依次计算：

1. 将当前位数a[i]和被加数plus相加；
2. a[i] = a[i] % 10; plus = plus/10;
3. 若plus>0，则在数组头部插入plus；

实现

void plusDigital(vector<int>& A, int digital)
{
    int val = digital;
    for(auto it=A.rbegin(); it!=A.rend(); ++it) {
        *it += val;
        val = *it / 10;
        *it %= 10;
    }
    
    if (val > 0) {
        A.insert(A.begin(), val);
    }
}

可以看出时间复杂度为O(n)，空间复杂度为O(1)。