LeetCode题练习与总结:加一--66-输入:digits = [0] 输出:[1] 提示:

时间:2024-04-15 06:56:16
  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

二、解题思路

  1. 首先,我们需要遍历数组的每一位数字,从最低位(数组的最后一个元素)开始。
  2. 对于每一位数字,我们将其加一。如果加一后的结果小于10,那么直接更新该位的数字,并且结束循环,因为我们已经完成了加一操作。
  3. 如果加一后的结果等于或大于10,说明发生了进位,我们需要将当前位的数字更新为0,并且继续处理下一位(即向前进位)。
  4. 如果在遍历完整个数组后,仍然有进位(即数组中所有的位都已经加一,且最后一个位加一后仍然等于或大于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)。

五、总结知识点