LeetCode-No.66. 加一

题目

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

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

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

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

• 1 <= digits.length <= 100

• 0 <= digits[i] <= 9

答案代码

"""
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

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

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

示例 3：
输入：digits = [0]
输出：[1]

提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
"""


class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        #代码1：
        """
        num = 0
        for i in digits:
            num = num * 10 + i
        num += 1
        return [int(i) for i in str(num)]
        """

        #代码2：
        # 从个位开始遍历
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0

        # 如果所有位都是9，则需要在最前面添加一位1
        return [1] + digits


if __name__ == '__main__':
    s = Solution()
    print(s.plusOne([1, 2, 3]))

if __name__ == '__main__':
    s = Solution()
    print(s.plusOne([4, 3, 2, 1]))

if __name__ == '__main__':
    s = Solution()
    print(s.plusOne([0]))

结果分析

时间复杂度

循环结构：该函数中有一个从列表末尾到开头的循环，其迭代次数取决于列表 digits 的长度，即 n。因此，最坏情况下需要遍历整个列表，时间复杂度为 O(n)。

最好情况：如果列表的最后一个数字不是9，那么只需要执行一次循环体内的操作，时间复杂度为 O(1)。

最坏情况：如果列表中的所有数字都是9，那么需要遍历整个列表，时间复杂度为 O(n)。

平均情况：平均而言，大约一半的元素会被遍历，因此平均时间复杂度接近 O(n/2)，但由于大O表示法忽略常数因子，因此平均时间复杂度仍然记作 O(n)。

列表拼接操作：在所有位都是9的情况下，需要创建一个新的列表 [1] 并与原列表拼接。这个操作的时间复杂度为 O(1)，因为它只涉及创建一个新的列表并将原列表附加在其后。

综上所述，该函数的时间复杂度为 O(n)。

空间复杂度

变量使用：在这个函数中，除了输入的 digits 列表外，没有使用其他额外的数据结构来存储数据。唯一可能增加空间复杂度的操作是在所有位都是9的情况下创建新的列表 [1] 和将原列表附加在其后。

列表拼接操作：在最坏情况下，当所有位都是9时，需要创建一个新列表，其长度为原列表长度加1，即 O(n+1)。然而，在大O表示法中，我们通常只保留最高阶项，因此空间复杂度为 O(n)。

综上所述，该函数的空间复杂度为 O(n)。