1. 问题背景与核心需求这道题目来自《剑指Offer》第66题是面试中考察数组操作和数学思维的经典问题。题目要求给定一个数组A[0,1,...,n-1]请构建一个数组B[0,1,...,n-1]其中B中的元素B[i]A[0]×A[1]×...×A[i-1]×A[i1]×...×A[n-1]。换句话说B[i]是A数组中除了A[i]之外所有元素的乘积。关键限制条件不能使用除法运算这个限制让问题变得更有挑战性。如果允许使用除法我们可以先计算整个数组的乘积然后对每个元素除以A[i]即可得到B[i]。但面试官通常会禁止这种解法因为它无法处理A[i]0的情况而且考察不出真实的算法能力。2. 暴力解法与复杂度分析最直观的解法是暴力计算对于每个B[i]都重新遍历整个数组A跳过A[i]计算乘积。这种方法的时间复杂度是O(n²)空间复杂度是O(1)不考虑输出数组B的空间。def constructArr(a): n len(a) b [1] * n for i in range(n): for j in range(n): if j ! i: b[i] * a[j] return b虽然这种解法简单直接但在面试中肯定无法让面试官满意。我们需要寻找更优的解法。3. 最优解法左右乘积数组3.1 解题思路我们可以将B[i]的乘积分解为两部分左半部分A[0] × A[1] × ... × A[i-1]右半部分A[i1] × A[i2] × ... × A[n-1]因此B[i] 左半部分乘积 × 右半部分乘积基于这个观察我们可以从左到右遍历数组计算每个元素左边所有元素的乘积存储在left数组中从右到左遍历数组计算每个元素右边所有元素的乘积存储在right数组中最后将left和right数组对应位置相乘得到最终结果3.2 具体实现def constructArr(a): n len(a) left [1] * n right [1] * n res [1] * n # 计算左半部分乘积 for i in range(1, n): left[i] left[i-1] * a[i-1] # 计算右半部分乘积 for i in range(n-2, -1, -1): right[i] right[i1] * a[i1] # 合并结果 for i in range(n): res[i] left[i] * right[i] return res这种方法的时间复杂度是O(n)因为我们进行了三次线性遍历空间复杂度是O(n)因为我们需要额外的left和right数组。3.3 空间优化我们可以进一步优化空间复杂度到O(1)不考虑输出数组的空间通过直接在结果数组上进行计算def constructArr(a): n len(a) res [1] * n # 先计算左半部分乘积 for i in range(1, n): res[i] res[i-1] * a[i-1] # 再用一个变量记录右半部分乘积并合并结果 right 1 for i in range(n-1, -1, -1): res[i] res[i] * right right * a[i] return res这个优化版本只需要常数级别的额外空间是面试中最希望看到的解法。4. 边界条件与测试用例在实现算法时需要考虑以下边界条件空数组输入单元素数组包含0的数组大数乘积考虑溢出问题测试用例示例# 正常情况 assert constructArr([1,2,3,4,5]) [120,60,40,30,24] # 包含0的情况 assert constructArr([1,0,3,4]) [0,12,0,0] # 单元素数组 assert constructArr([5]) [1] # 空数组 assert constructArr([]) []5. 面试中的常见问题在面试中面试官可能会追问以下问题为什么不能使用除法如果允许使用除法解法会有什么变化如何处理大数相乘导致的溢出问题如果数组中有多个0结果会怎样如何将这个解法扩展到多维数组对于问题2可以考虑使用对数转换将乘法转换为加法或者使用大整数类来处理。对于问题4可以考虑将多维数组展平为一维数组处理或者使用分治策略。6. 实际应用场景虽然这个问题看起来是纯算法题但它有实际的应用背景图像处理中的滤波器计算统计学中的某些特征计算金融领域中的累积收益率计算信号处理中的滑动窗口计算理解这个问题的解法有助于我们在实际工作中遇到类似问题时快速找到解决方案。7. 算法扩展与变种这个问题有几个有趣的变种允许使用除法时的解法计算前i个元素的乘积前缀积计算任意区间[i,j]的乘积在线版本数据流情况下如何维护乘积对于变种3我们可以预先计算前缀积数组然后区间[i,j]的乘积等于prefix[j1]/prefix[i]假设i≤j。如果数组中有0需要特殊处理。8. 性能优化技巧在实际实现时可以考虑以下优化使用位运算代替部分乘法当元素是2的幂次时并行计算左右乘积对于大规模数组使用SIMD指令加速向量化计算对于稀疏数组很多1或0可以特殊处理虽然这些优化在面试中不一定会被问到但在实际工程应用中可能很有价值。9. 不同语言的实现差异虽然算法思想相同但在不同语言中实现时会有细微差别C实现需要注意vectorint constructArr(vectorint a) { int n a.size(); vectorint res(n, 1); for (int i 1; i n; i) { res[i] res[i-1] * a[i-1]; } int right 1; for (int i n-1; i 0; --i) { res[i] * right; right * a[i]; } return res; }Java实现需要注意数组初始化和边界检查public int[] constructArr(int[] a) { if (a null || a.length 0) return new int[0]; int n a.length; int[] res new int[n]; Arrays.fill(res, 1); for (int i 1; i n; i) { res[i] res[i-1] * a[i-1]; } int right 1; for (int i n-1; i 0; i--) { res[i] * right; right * a[i]; } return res; }10. 常见错误与调试技巧在实现这个算法时容易犯以下错误初始值设置不正确特别是right的初始值边界条件处理不当如i0或in-1时乘积顺序错误先乘还是先更新right数组越界访问调试时可以打印中间结果left和right数组对小规模测试用例手动计算验证使用断言检查不变式逐步调试观察变量变化例如对于输入[1,2,3,4]正确的中间结果应该是left [1, 1, 2, 6]right [24, 12, 4, 1]最终结果 [24, 12, 8, 6]如果在某一步发现结果不符可以快速定位问题所在。
1. 问题背景与核心需求这道题目来自《剑指Offer》第66题是面试中考察数组操作和数学思维的经典问题。题目要求给定一个数组A[0,1,...,n-1]请构建一个数组B[0,1,...,n-1]其中B中的元素B[i]A[0]×A[1]×...×A[i-1]×A[i1]×...×A[n-1]。换句话说B[i]是A数组中除了A[i]之外所有元素的乘积。关键限制条件不能使用除法运算这个限制让问题变得更有挑战性。如果允许使用除法我们可以先计算整个数组的乘积然后对每个元素除以A[i]即可得到B[i]。但面试官通常会禁止这种解法因为它无法处理A[i]0的情况而且考察不出真实的算法能力。2. 暴力解法与复杂度分析最直观的解法是暴力计算对于每个B[i]都重新遍历整个数组A跳过A[i]计算乘积。这种方法的时间复杂度是O(n²)空间复杂度是O(1)不考虑输出数组B的空间。def constructArr(a): n len(a) b [1] * n for i in range(n): for j in range(n): if j ! i: b[i] * a[j] return b虽然这种解法简单直接但在面试中肯定无法让面试官满意。我们需要寻找更优的解法。3. 最优解法左右乘积数组3.1 解题思路我们可以将B[i]的乘积分解为两部分左半部分A[0] × A[1] × ... × A[i-1]右半部分A[i1] × A[i2] × ... × A[n-1]因此B[i] 左半部分乘积 × 右半部分乘积基于这个观察我们可以从左到右遍历数组计算每个元素左边所有元素的乘积存储在left数组中从右到左遍历数组计算每个元素右边所有元素的乘积存储在right数组中最后将left和right数组对应位置相乘得到最终结果3.2 具体实现def constructArr(a): n len(a) left [1] * n right [1] * n res [1] * n # 计算左半部分乘积 for i in range(1, n): left[i] left[i-1] * a[i-1] # 计算右半部分乘积 for i in range(n-2, -1, -1): right[i] right[i1] * a[i1] # 合并结果 for i in range(n): res[i] left[i] * right[i] return res这种方法的时间复杂度是O(n)因为我们进行了三次线性遍历空间复杂度是O(n)因为我们需要额外的left和right数组。3.3 空间优化我们可以进一步优化空间复杂度到O(1)不考虑输出数组的空间通过直接在结果数组上进行计算def constructArr(a): n len(a) res [1] * n # 先计算左半部分乘积 for i in range(1, n): res[i] res[i-1] * a[i-1] # 再用一个变量记录右半部分乘积并合并结果 right 1 for i in range(n-1, -1, -1): res[i] res[i] * right right * a[i] return res这个优化版本只需要常数级别的额外空间是面试中最希望看到的解法。4. 边界条件与测试用例在实现算法时需要考虑以下边界条件空数组输入单元素数组包含0的数组大数乘积考虑溢出问题测试用例示例# 正常情况 assert constructArr([1,2,3,4,5]) [120,60,40,30,24] # 包含0的情况 assert constructArr([1,0,3,4]) [0,12,0,0] # 单元素数组 assert constructArr([5]) [1] # 空数组 assert constructArr([]) []5. 面试中的常见问题在面试中面试官可能会追问以下问题为什么不能使用除法如果允许使用除法解法会有什么变化如何处理大数相乘导致的溢出问题如果数组中有多个0结果会怎样如何将这个解法扩展到多维数组对于问题2可以考虑使用对数转换将乘法转换为加法或者使用大整数类来处理。对于问题4可以考虑将多维数组展平为一维数组处理或者使用分治策略。6. 实际应用场景虽然这个问题看起来是纯算法题但它有实际的应用背景图像处理中的滤波器计算统计学中的某些特征计算金融领域中的累积收益率计算信号处理中的滑动窗口计算理解这个问题的解法有助于我们在实际工作中遇到类似问题时快速找到解决方案。7. 算法扩展与变种这个问题有几个有趣的变种允许使用除法时的解法计算前i个元素的乘积前缀积计算任意区间[i,j]的乘积在线版本数据流情况下如何维护乘积对于变种3我们可以预先计算前缀积数组然后区间[i,j]的乘积等于prefix[j1]/prefix[i]假设i≤j。如果数组中有0需要特殊处理。8. 性能优化技巧在实际实现时可以考虑以下优化使用位运算代替部分乘法当元素是2的幂次时并行计算左右乘积对于大规模数组使用SIMD指令加速向量化计算对于稀疏数组很多1或0可以特殊处理虽然这些优化在面试中不一定会被问到但在实际工程应用中可能很有价值。9. 不同语言的实现差异虽然算法思想相同但在不同语言中实现时会有细微差别C实现需要注意vectorint constructArr(vectorint a) { int n a.size(); vectorint res(n, 1); for (int i 1; i n; i) { res[i] res[i-1] * a[i-1]; } int right 1; for (int i n-1; i 0; --i) { res[i] * right; right * a[i]; } return res; }Java实现需要注意数组初始化和边界检查public int[] constructArr(int[] a) { if (a null || a.length 0) return new int[0]; int n a.length; int[] res new int[n]; Arrays.fill(res, 1); for (int i 1; i n; i) { res[i] res[i-1] * a[i-1]; } int right 1; for (int i n-1; i 0; i--) { res[i] * right; right * a[i]; } return res; }10. 常见错误与调试技巧在实现这个算法时容易犯以下错误初始值设置不正确特别是right的初始值边界条件处理不当如i0或in-1时乘积顺序错误先乘还是先更新right数组越界访问调试时可以打印中间结果left和right数组对小规模测试用例手动计算验证使用断言检查不变式逐步调试观察变量变化例如对于输入[1,2,3,4]正确的中间结果应该是left [1, 1, 2, 6]right [24, 12, 4, 1]最终结果 [24, 12, 8, 6]如果在某一步发现结果不符可以快速定位问题所在。
