题目描述
给定一个由整数组成的非空数组所表示的非负整数, 在该数的基础上加一.
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字.
你可以假设除了整数 0 之外, 这个整数不会以零开头.
示例:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123.
思路
使用数组来模拟人做加减乘除的方法. 代码如下:
- class Solution {
- public:
- vector<int> plusOne(vector<int>& digits) {
- if(digits.empty())
- return {};
- if(digits[digits.size()-1]<9){ // 如果最后一个数字小于 9, 加一后返回, 避免不必要的遍历
- digits[digits.size()-1]++;
- return digits;
- }
- int carry=1; // 进位, 因为是加 1, 所以进位初始化为 1
- for(int i=digits.size()-1; i>=0; i--){
- int s = digits[i]+carry;
- if(s>9){ // 产生进位
- carry = s/10;
- s%=10;
- digits[i] = s;
- if(i==0){ // 如果第一位产生进位, 则在首位插入 1
- digits.insert(digits.begin(), 1);
- }
- } else {
- digits[i] = s;
- carry=0;
- }
- }
- return digits;
- }
- };
时间复杂度: O(n)
最好情况下为 O(1)(加一后没有进位), 最差为 O(n)(加一后产生进位, 则需要遍历数组一遍).
空间复杂度: O(1)
申请的额外内存不随输入规模的增大而增大.
来源: http://www.bubuko.com/infodetail-3495807.html