作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在列表的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
输入格式
- digits：一个整数数组。
输出格式
- 返回一个数组，表示加一后的结果。
示例
示例 1
输入: digits = [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例 2
输入: digits = [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。
示例 3
输入: digits = [9] 输出: [1,0] 解释: 输入数组表示数字 9。
方法一：模拟进位
解题步骤
- 从最低位开始遍历：遍历数组的最后一个元素，即数字的最低位。
- 处理进位：如果当前位加一后等于10，则设置当前位为0，并将进位带到下一位。
- 终止条件：如果没有进位发生，直接返回数组。如果遍历完所有元素仍有进位，需要在数组最前面添加一个元素1。
完整的规范代码
def plusOne(digits): """ 使用模拟进位法对数组表示的数字进行加一操作 :param digits: List[int], 代表数字的数组 :return: List[int], 加一后的数组 """ n = len(digits) for i in range(n-1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 return [1] + digits # 处理全部为9的情况 # 示例调用 print(plusOne([1,2,3])) # 输出: [1,2,4] print(plusOne([4,3,2,1])) # 输出: [4,3,2,2] print(plusOne([9])) # 输出: [1,0]
算法分析
- 时间复杂度：(O(n))，在最坏的情况下需要遍历整个数组。
- 空间复杂度：(O(1))，除了输出数组外，额外使用的空间是常数级别的。
方法二：转换为数字
解题步骤
- 数组转换为数字：将数组转换为整数。
- 加一操作：对该数字加一。
- 数字转回数组：将结果数字转换回数组形式。
完整的规范代码
def plusOne(digits): """ 将数组转换为数字进行加一，然后再转换回数组 :param digits: List[int], 代表数字的数组 :return: List[int], 加一后的数组 """ num = 0 for digit in digits: num = num * 10 + digit num += 1 return [int(i) for i in str(num)] # 示例调用 print(plusOne([1,2,3])) # 输出: [1,2,4] print(plusOne([4,3,2,1])) # 输出: [4,3,2,2] print(plusOne([9])) # 输出: [1,0]
算法分析
- 时间复杂度：(O(n))，转换过程中涉及到线性时间的操作。
- 空间复杂度：(O(n))，需要存储转换后的数字和结果数组。
方法三：字符串处理
解题步骤
- 数组转字符串：将数组中的数字转换成字符串并连接。
- 字符串转数字加一：将字符串转换为数字进行加一操作。
- 数字转字符串再转数组：将加一后的数字转换为字符串，然后将每个字符转换为整数数组。
完整的规范代码
def plusOne(digits): """ 使用字符串处理的方法进行加一操作 :param digits: List[int], 代表数字的数组 :return: List[int], 加一后的数组 """ s = ''.join(map(str, digits)) num = int(s) + 1 return [int(x) for x in str(num)] # 示例调用 print(plusOne([1,2,3])) # 输出: [1,2,4] print(plusOne([4,3,2,1])) # 输出: [4,3,2,2] print(plusOne([9])) # 输出: [1,0]
算法分析
- 时间复杂度：(O(n))，涉及字符串和数字的转换。
- 空间复杂度：(O(n))，需要额外的空间来存储字符串和结果数组。
方法四：递归处理
解题步骤
- 定义递归函数：递归处理加一和进位。
- 边界条件：当处理到第一个数字且需要进位时，在数组前添加一个1。
- 递归逻辑：从后向前处理每个数字，处理进位。
完整的规范代码
def plusOne(digits): """ 使用递归处理数组加一的操作 :param digits: List[int], 代表数字的数组 :return: List[int], 加一后的数组 """ def helper(index): if index < 0: digits.insert(0, 1) return if digits[index] == 9: digits[index] = 0 helper(index - 1) else: digits[index] += 1 helper(len(digits) - 1) return digits # 示例调用 print(plusOne([1,2,3])) # 输出: [1,2,4] print(plusOne([4,3,2,1])) # 输出: [4,3,2,2] print(plusOne([9])) # 输出: [1,0]
算法分析
- 时间复杂度：(O(n))，最坏情况下需要递归遍历整个数组。
- 空间复杂度：(O(n))，递归深度可能达到数组长度。
方法五：迭代优化
解题步骤
- 从最后一个元素开始迭代：处理每个元素的加一和进位。
- 处理进位：如果当前位置变为10，则设置为0并继续处理前一位。
- 处理全部为9的特殊情况：如果首位也进位，则数组前添加1。
完整的规范代码
def plusOne(digits): """ 使用迭代优化的方法处理加一操作 :param digits: List[int], 代表数字的数组 :return: List[int], 加一后的数组 """ for i in range(len(digits) - 1, -1, -1): if digits[i] == 9: digits[i] = 0 else: digits[i] += 1 return digits digits.insert(0, 1) return digits # 示例调用 print(plusOne([1,2,3])) # 输出: [1,2,4] print(plusOne([4,3,2,1])) # 输出: [4,3,2,2] print(plusOne([9])) # 输出: [1,0]
算法分析
- 时间复杂度：(O(n))，遍历数组进行处理。
- 空间复杂度：(O(1))，除了结果外，几乎不使用额外空间。
不同算法的优劣势对比
| 特征 | 方法一: 模拟进位 | 方法二: 转数字 | 方法三: 字符串处理 | 方法四: 递归 | 方法五: 迭代优化 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(n)) | (O(n)) | (O(n)) | (O(1)) |
| 优势 | 直接明了，逻辑简单 | 数字操作直观 | 代码简洁，易理解 | 自然的递归逻辑 | 极简实现，高效处理 |
| 劣势 | 处理9的进位较多 | 处理大数可能溢出 | 大数转换成本高 | 栈溢出风险 | 特殊情况多一个步骤 |
应用示例
会计软件：
在处理财务数据时，经常需要对大量的数字序列进行加减操作。这些算法可用于实现一些基本的数字操作功能，如自动递增发票号或处理交易记录。特别是在需要快速响应和高效计算的场景中，选择合适的算法可以显著提高软件性能和用户满意度。
欢迎关注微信公众号 数据分析螺丝钉
