[0066] Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.

Test Case

Given	When	Then
nums = [1, 2, 3]	Plus One	return [1, 2, 4]]
nums = [9,8,7,6,5,4,3,2,1,0]	Plus One	return [9,8,7,6,5,4,3,2,1,1]

Solution

1. Brute-force Solution

逆序遍历数组，对每个item进行加一并判断是否需要进位,不需要返回数组,需要的话则继续遍历,如果最后一位仍需要进位,则构建一个数组长度加一首位为一其他用零填充的数组

public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) {
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

复杂度分析

• 时间复杂度: O(n)

  假设数组长度为n,那么最多执行N步,因此时间复杂度为 O(n)。

• 空间复杂度: O(n)

  该算法中占用存储空间n+1,因此空间复杂度为 O(n)