本文主要是介绍数组题目：加一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：加一
出处：66. 加一
难度
3 级
题目描述
要求
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 \texttt{0} 0 之外，这个整数不会以零开头。
示例
示例 1：
输入： digits = [1,2,3] \texttt{digits = [1,2,3]} digits = [1,2,3]
输出： [1,2,4] \texttt{[1,2,4]} [1,2,4]
解释：输入数组表示数字 123 \texttt{123} 123。
示例 2：
输入： digits = [4,3,2,1] \texttt{digits = [4,3,2,1]} digits = [4,3,2,1]
输出： [4,3,2,2] \texttt{[4,3,2,2]} [4,3,2,2]
解释：输入数组表示数字 4321 \texttt{4321} 4321。
示例 3：
输入： digits = [0] \texttt{digits = [0]} digits = [0]
输出： [1] \texttt{[1]} [1]
数据范围
- 1 ≤ digits.length ≤ 100 \texttt{1} \le \texttt{digits.length} \le \texttt{100} 1≤digits.length≤100
- 0 ≤ digits[i] ≤ 9 \texttt{0} \le \texttt{digits[i]} \le \texttt{9} 0≤digits[i]≤9
解法
思路和算法
将一个非负整数加一，得到的新数的长度可能和原数的长度相同，也可能比原数的长度多 1 1 1 位。只有当原数的每一位都是 9 9 9 时，新数的长度才会比原数的长度多 1 1 1 位。
模拟加法过程即可。首先将数组 digits \textit{digits} digits 的右边第一位加 1 1 1，如果在更新之后，第一位大于 9 9 9，则产生进位，将第二位加 1 1 1，第一位保留个位。如果在进位操作之后，第二位大于 9 9 9，则继续处理进位，直到处理到最高位，或者进位不再产生大于 9 9 9 的位。
如果最高位大于 9 9 9，则新数的长度比元素的长度多 1 1 1 位，新数只有最高位是 1 1 1，其余每一位都是 0 0 0，因此创建新数组，将新数组的最高位设为 1 1 1 并返回。
如果最高位不大于 9 9 9，则返回更新后的数组 digits \textit{digits} digits。
代码
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;}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 digits \textit{digits} digits 的长度。需要反向遍历数组 digits \textit{digits} digits 一次，更新数组中的元素或者创建新数组。
-
空间复杂度： O ( 1 ) O(1) O(1)。除了返回值以外，使用的空间复杂度是常数。
这篇关于数组题目：加一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
