66.加1

目次

一、问题形貌
二、解题思绪
三、代码
四、复杂度分析

---

一、问题形貌

给定一个由 整数 构成的 非空 数组所表示的非负整数，在该数的底子上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
二、解题思绪

• 从数组的 末了一位（最低位） 开始加 1；
  
• 假如这一位加完不是 10，就直接返回；
  
• 假如是 10，就酿成 0，然后进位，继续处理前一位；
  
• 假如最前一位也进位了，比如 [9,9,9]，末了就需要在最前面插入一个 1。
  

三、代码

1. class Solution {
2. public:
3.     vector<int> plusOne(vector<int>& digits) {
4.         // 从最后一位开始处理进位
5.         for (int i = digits.size() - 1; i >= 0; i--) {
6.             if (digits[i] < 9) {
7.                 // 如果当前位小于 9，直接加一，后面不用处理了
8.                 digits[i]++;
9.                 return digits;
10.             }
11.             // 当前位是 9，加一会变成 10，要进位，当前位变成 0
12.             digits[i] = 0;
13.         }
15.         // 如果全部都进位了，例如 999 → 1000
16.         // 最终结果需要在最前面插入一个 1
17.         digits.insert(digits.begin(), 1);
18.         return digits;
19.     }
20. };

复制代码

四、复杂度分析

• 时间复杂度： O(n)（最坏情况下需要遍历整个数组）
  
• 空间复杂度： O(1)（假如允许修改输入数组）
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。