【力扣-238. 除了自身以外数组的乘积 ✨】Python笔记

前置知识点Python实用技巧在解决算法问题时掌握一些Python高级工具能大幅提升效率collections.defaultdict(int)用于自动初始化字典的默认值。当访问不存在的键时会自动赋值为0非常适合统计频率的场景from collections import defaultdict count defaultdict(int) count[a] 1 # 无需判断键是否存在float(inf)表示数学上的无穷大常用于初始化比较操作min_val float(inf) for num in [3,1,4]: min_val min(min_val, num) # 自动处理初始比较问题分析LeetCode 238给定整数数组nums要求返回新数组answer其中answer[i]等于nums中除nums[i]外所有元素的乘积。限制条件不能使用除法运算时间复杂度O(n)空间复杂度O(1)不计输出数组解法一左右乘积数组构建两个辅助数组left[i]存储nums[i]左侧所有元素乘积right[i]存储nums[i]右侧所有元素乘积def productExceptSelf(nums): n len(nums) left, right [1]*n, [1]*n for i in range(1, n): left[i] left[i-1] * nums[i-1] for i in range(n-2, -1, -1): right[i] right[i1] * nums[i1] return [left[i]*right[i] for i in range(n)]解法二空间优化版利用输出数组动态存储中间结果将空间复杂度优化到O(1)def productExceptSelf(nums): n len(nums) res [1] * n # 存储左侧乘积 for i in range(1, n): res[i] res[i-1] * nums[i-1] # 动态计算右侧乘积 R 1 for i in range(n-1, -1, -1): res[i] * R R * nums[i] return res复杂度分析时间复杂度两种解法均为O(n)需要两次线性遍历。空间复杂度解法一需要O(n)额外空间解法二优化到O(1)输出数组不计。应用场景扩展这种左右分解的思想还可应用于接雨水问题股票买卖问题任何需要前后缀信息的数组处理掌握这种预处理技巧能有效解决许多数组相关的算法难题。