Plus One

Question

Problem Statement

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Example

Given [1,2,3] which represents 123, return [1,2,4].

Given [9,9,9] which represents 999, return [1,0,0,0].

题解

C++

class Solution {
public:
/**
* @param digits a number represented as an array of digits
* @return the result
*/
vector<int> plusOne(vector<int>& digits) {
return plusN(digits, 1);
}

vector<int> plusN(vector<int>& digits, int n) {
vector<int> result;
int carry = n;
for (int i = digits.size() - 1; i >= 0; i--) {
result.insert(result.begin(), (digits[i] + carry) % 10);
carry = (digits[i] + carry) / 10;
}
if (carry) result.insert(result.begin(), carry);
return result;
}
};


Java

public class Solution {
/**
* @param digits a number represented as an array of digits
* @return the result
*/
public int[] plusOne(int[] digits) {
return plusDigit(digits, 1);
}

private int[] plusDigit(int[] digits, int digit) {
if (digits == null || digits.length == 0) return null;

// regard digit(0~9) as carry
int carry = digit;
int[] result = new int[digits.length];
for (int i = digits.length - 1; i >= 0; i--) {
result[i] = (digits[i] + carry) % 10;
carry = (digits[i] + carry) / 10;
}

// carry == 1
if (carry == 1) {
int[] finalResult = new int[result.length + 1];
finalResult[0] = 1;
return finalResult;
}

return result;
}
}


复杂度分析

Java 中需要返回数组，而这个数组在处理之前是不知道大小的，故需要对最后一个进位单独处理。时间复杂度 $O(n)$, 空间复杂度在最后一位有进位时恶化为 $O(n)$, 当然也可以通过两次循环使得空间复杂度为 $O(1)$.

Reference

• Soulmachine 的 leetcode 题解，将要加的数当做进位处理就是从这学到的。