加一
WangScaler: 一个用心创作的作者。声明:才疏学浅,如有错误,恳请指正。
题目
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
分析
这个题其实就是把一个正数拆分下来的每个数放进数组里给你,你把加一之后的数,再放进数组里。这只是简单的理解,如果你真这么写就麻烦了,首先你得把数组拼接回数字,需要遍历一遍,加一之后,再放回数组,再遍历一遍,这样无疑是很麻烦的一件事。上面的程序只是对题意得简单理解就是数字加一。
在数组里进行操作无疑是一件简单得事,那么我们怎么处理呢?
- 数组的最后一位如果小于9,那么你需要把最后一位置加一。
- 数组的最后一位是9,且数组的长度大于等于2,那么需要把最后一位置0,上一位加一。
- 数组最后一位是9,前边加一也是9,直到没有最后一位进行加一,那么需要扩容,第一位为1,其他的为0。
把这三个条件实现,那么答案也就出来了。
答案
class Solution {
public int[] plusOne(int[] digits) {
int lastNum = digits[digits.length - 1];
int i = 1;
while (lastNum == 9 && digits.length > i) {
digits[digits.length - i] = 0;
++i;
lastNum = digits[digits.length - i];
}
if (i == digits.length && lastNum == 9) {
int[] digitsNew = new int[digits.length + 1];
digitsNew[0] = 1;
digits = digitsNew;
}else{
digits[digits.length - i] = lastNum + 1;
}
return digits;
}
}
复杂度
- 时间复杂度:O(n),最差的情况就是遍历整个数组。
- 空间复杂度:O(1),我们只需要几个变量记录我们的数据,比如前一个数字的大小,以及遍历的位置,以及为了扩容新创建的数组。
总结
这个题本质上就是数字加一,只不过把数字通过数组来呈现。最难处理的就是数组长度不够用的情况,其实new出来的数组的默认值就是0,所以我们直接把第一个位置修改为1即可,简单快捷,也没什么太大的难度。
都来了,点个赞再走呗!关注WangScaler,祝你升职、加薪、不提桶!