1 <= digits.length <= 100
0 <= digits[i] <= 9
二、解题思路
- 首先,我们需要遍历数组的每一位数字,从最低位(数组的最后一个元素)开始。
- 对于每一位数字,我们将其加一。如果加一后的结果小于10,那么直接更新该位的数字,并且结束循环,因为我们已经完成了加一操作。
- 如果加一后的结果等于或大于10,说明发生了进位,我们需要将当前位的数字更新为0,并且继续处理下一位(即向前进位)。
- 如果在遍历完整个数组后,仍然有进位(即数组中所有的位都已经加一,且最后一个位加一后仍然等于或大于10),我们需要在数组的开头添加一个1,表示进位到了最高位。
三、具体代码
public class Solution {
public int[] plusOne(int[] digits) {
// 从数组的最后一个元素开始,向前遍历
for (int i = digits.length - 1; i >= 0; i--) {
// 如果当前位加一后小于10,直接更新并结束循环
if (digits[i] < 9) {
digits[i]++;
return digits;
} else {
// 如果当前位加一后等于或大于10,发生进位
digits[i] = 0; // 将当前位更新为0,并继续向前一位进位
}
}
// 如果所有的位都已经加一,且仍然有进位,需要在数组开头添加一个1
int[] result = new int[digits.length + 1];
result[0] = 1; // 在新数组的第一个位置添加1
return result;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 该算法的主要操作是遍历整数数组的每一位数字,并对其进行加法操作。这个操作是线性的,即它与输入数组的长度成正比。
- 遍历数组的时间复杂度为 O(n),其中 n 是数组
digits
的长度。
- 由于在遍历过程中可能需要遍历整个数组,或者在最坏的情况下(即数组中的每个数字都是9)需要遍历整个数组并再进行一次操作(在数组前面添加一个新元素)。
- 所以总的时间复杂度仍然是 O(n)。
2. 空间复杂度
- 空间复杂度主要取决于存储操作的额外空间需求。
- 在大多数情况下,我们只需要原始数组
digits
的空间来存储结果,因此空间复杂度为 O(n)。
- 但是,在最坏的情况下,当数组中的每个数字都是9时,我们需要创建一个新的数组来存储结果(因为需要在数组前面添加一个1),这将导致额外的 O(n) 空间需求。
- 因此,总的空间复杂度为 O(n)。
五、总结知识点
-