Leetcode 题解|66. 加一

题目

---

66. 加一

用一个由int类型正整数组成，且元素大于1的数组来表示一个非负整数。实现一个函数对这个非负整数加一。高位在前地位在后，数组中每个元素的范围0~9。且除了整数0以外 [0] ，这个整数不会以零开头。

Simple One:

输入: [2,3,4] 输出: [2,3,5] 解释: 输入数组表示数字 234。输出235。

Simple Two:

输入: [9,9,9,9] 输出: [1,0,0,0,0] 解释: 输入数组表示数字 9999。输出10000.

题目分析

---

获取数组最后一位索引idx，反向遍历，也就是从代表的整数的个位开始判断。如果最个位数不等于9，就直接数组最后一个元素+1.跳出循环。如果个位等于9，个位0，继续循环，根据1的条件判断百位。重复2-3直到跳出循环或者循环结束。当循环结束后如果最高位为0，说明已经进位到高位了。那么需要再数组最前面插入一个元素为1. 例如 999 + 1 = 1000;

复杂度分析

时间复杂度：O(n)， 假设数组总共有 n 个元素，至多遍历 n 步。空间复杂度：O(1)。

Java

class Solution { public int[] plusOne(int[] digits) { int idx = digits.length - 1; while (idx >= 0) { if (digits[idx] == 9) { digits[idx] = 0; } else { digits[idx] = digits[idx] + 1; break; } idx --; } if (digits[0] == 0) { digits = new int[digits.length + 1]; digits[0] = 1; } return digits; } }

Swift

class Solution { func plusOne(_ digits: [Int]) -> [Int] { var idx = digits.count - 1 var results = digits while (idx >= 0) { if (results[idx] == 9) { results[idx] = 0 } else { results[idx] = results[idx] + 1 break } idx -= 1 } if (results[0] == 0) { results = [Int](repeating: 0, count: digits.count + 1) results[0] = 1 } return results } }

JavaScript

var plusOne = function(digits) { var idx = digits.length - 1; while (idx >= 0) { if (digits[idx] == 9) { digits[idx] = 0; } else { digits[idx] = digits[idx] + 1; break; } idx --; } if (digits[0] == 0) { digits.unshift(1); } return digits; };