题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

样例

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

算法1

(模拟) $O(n)$

模拟加法竖式;
如果发现不会进位了，可以提前返回结果。

时间复杂度

遍历数组一次，时间复杂度$O(n)$；
最后一次如果要在头部插入一个元素，时间复杂度是$O(n)$；
故最坏情况也就是$O(n)$

参考文献

C++ 代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size(), add = 1;
        for (int i = n - 1; i >= 0; --i){
            digits[i] += add;
            add = digits[i] / 10;
            if (!add) return digits; // 如果发现不会进位了，可以提前返回结果
            digits[i] %= 10;
        }

        if (add) digits.insert(digits.begin(), add);
        return digits;
    }
};