加一

66. 加一

直接上代码

    //时间复杂度是O(N)，空间复杂度O(N)
    public int[] plusOne(int[] digits) {
        int n = digits.length - 1;
        digits[n] += 1;
        for (int i = n; i > 0 && digits[i] == 10; i--) {
            digits[i] = 0;
            digits[i - 1] += 1;
        }
        if (digits[0] != 10) return digits;
        else {
            digits[0] = 0;
            int[] temp = new int[digits.length + 1];
            temp[0] = 1;
            System.arraycopy(digits, 0, temp, 1, digits.length);
            return temp;
        }
    }

Tips:

• 本质是小学按位相加，传播进位
• 每次遍历一个数组元素，时间复杂度显而易见
• 至于空间复杂度高完全是因为给你的是数组，返回的也是数组，如果是List<Integer>的链表完全可以O(1)