题目

标题和出处

标题：加一

出处：66. 加一

难度

3 级

题目描述

要求

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

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

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

示例

示例 1：

输入：
输出：
解释：输入数组表示数字 。

示例 2：

输入：
输出：
解释：输入数组表示数字 。

示例 3：

输入：
输出：

数据范围

解法

思路和算法

将一个非负整数加一，得到的新数的长度可能和原数的长度相同，也可能比原数的长度多 位。只有当原数的每一位都是 时，新数的长度才会比原数的长度多 位。

模拟加法过程即可。首先将数组 的右边第一位加 ，如果在更新之后，第一位大于 ，则产生进位，将第二位加 ，第一位保留个位。如果在进位操作之后，第二位大于 ，则继续处理进位，直到处理到最高位，或者进位不再产生大于 的位。

如果最高位大于 ，则新数的长度比元素的长度多 位，新数只有最高位是 ，其余每一位都是 ，因此创建新数组，将新数组的最高位设为 并返回。

如果最高位不大于 ，则返回更新后的数组 。

代码

class Solution {
    public int[] plusOne(int[] digits) {
        int length = digits.length;
        int index = length - 1;
        digits[index]++;
        while (index > 0 && digits[index] > 9) {
            digits[index - 1] += digits[index] / 10;
            digits[index] %= 10;
            index--;
        }
        if (digits[0] > 9) {
            digits = new int[length + 1];
            digits[0] = 1;
        }
        return digits;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=ChsQC)，其中 是数组 的长度。需要反向遍历数组 一次，更新数组中的元素或者创建新数组。
• 空间复杂度：#card=math&code=O%281%29&id=m5pQm)。除了返回值以外，使用的空间复杂度是常数。