Tags: 数组
题目
用一个由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;
};