数组加一算法：小数组正常运行，大数组计算出错求助

问题描述 #

给定一个以整数数组digits表示的大整数，其中digits[i]是该整数的第i位数字。数字从左到右按从最高位到最低位的顺序排列，且该大整数没有前导零。
将这个大整数加一，并返回结果数字数组。

遇到的问题 #

• 输入：[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]
• 实际输出：[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,4,0,9]
• 预期输出：[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4]

注：代码在输入[1,2,3]时可正常运行。

原思路与代码 #

原思路是将数组转换为十进制整数计算：例如[4,2,3]转换为4*10^2 + 2*10^1 + 3*10^0，加一后再拆分为数组。

#include <stdio.h>
#include <math.h>
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        long long n = digits.size();
        long long s = 0;
        for( int i = 0; i < n; i++){
          s += digits[i]*(pow(10,(n-(i+1)))); 
        }
        s+=1;
        vector<int> ndig;
        while (s){
            ndig.insert(ndig.begin(),s%10);
            s/=10;
        }
        return ndig;
    }
};

问题原因 #

1. 浮点数精度误差：pow(10, x)是浮点数运算函数，当指数较大时（比如数组长度19位，指数达18），浮点数无法精确表示超大整数，导致计算s时出现数值偏差，最终转换回数组时数字错位。
2. 数值溢出风险：即使使用long long，当数组长度超过19位时，也会超出其存储范围，直接导致计算错误。

修复方案 #

直接操作数组，从末尾开始处理进位，完全避免数值转换：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        // 从最后一位开始遍历处理进位
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                digits[i]++;
                return digits;
            }
            // 当前位是9，加1后变为0，继续向前进位
            digits[i] = 0;
        }
        // 所有位都是9，需在开头新增一位1
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

修复逻辑说明 #

• 从数组末尾逐位检查：若当前位不是9，直接加1后返回数组，无需后续处理。
• 若当前位是9，加1后变为0，继续向前一位进位。
• 若遍历完所有位仍未返回，说明所有位都是9，此时在数组开头插入1即可（如[9,9,9]加一后变为[1,0,0,0]）。

内容的提问来源于stack exchange，提问作者Praneel65