首页/新闻资讯/正文详情

高效解决数组乘积问题:前缀与后缀积算法详解

发布时间:2026/11/5 7:13:37 来源:云帆数科 栏目:资讯中心
高效解决数组乘积问题:前缀与后缀积算法详解
## 1. 问题背景与核心需求 这道算法题看似简单却暗藏玄机。给定一个整数数组nums要求返回一个新数组answer其中answer[i]等于nums中除nums[i]之外所有元素的乘积。题目明确要求不能使用除法运算且时间复杂度必须控制在O(n)内。 我第一次遇到这个问题是在某大厂的面试现场当时下意识想用暴力解法但面试官紧接着追加了时间复杂度限制。这让我意识到这类题目考察的不仅是基础编码能力更是对空间换时间、预处理技巧等核心算法思维的掌握程度。 ## 2. 暴力解法与优化方向 ### 2.1 直观解法及其缺陷 最直接的思路是双层循环遍历 python def productExceptSelf(nums): n len(nums) answer [1] * n for i in range(n): for j in range(n): if i ! j: answer[i] * nums[j] return answer这种解法时间复杂度O(n²)当n1e5时计算量会达到1e10次操作完全无法接受。即使采用预先计算总乘积再除以当前元素的方法时间复杂度O(n)也因题目禁止使用除法而不可行。2.2 关键突破口分析通过绘制乘积关系图可以发现每个位置的输出实际等于其左侧所有元素的乘积乘以右侧所有元素的乘积。例如对于数组[1,2,3,4]answer[2] 左侧(1×2) × 右侧(4) 8answer[1] 左侧(1) × 右侧(3×4) 12这种左右分解的思路将问题转化为两个独立的子问题计算每个元素左侧所有元素的乘积前缀积计算每个元素右侧所有元素的乘积后缀积3. 最优解实现方案3.1 空间O(n)的标准解法def productExceptSelf(nums): n len(nums) left [1] * n right [1] * n answer [1] * n # 计算左侧乘积 for i in range(1, n): left[i] left[i-1] * nums[i-1] # 计算右侧乘积 for j in range(n-2, -1, -1): right[j] right[j1] * nums[j1] # 合并结果 for k in range(n): answer[k] left[k] * right[k] return answer这种方法需要额外的left和right数组空间复杂度O(n)。虽然满足时间复杂度要求但仍有优化空间。3.2 空间O(1)的进阶解法输出数组不计入空间def productExceptSelf(nums): n len(nums) answer [1] * n # 先用answer存储左侧乘积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 动态计算右侧乘积并直接相乘 right 1 for j in range(n-1, -1, -1): answer[j] * right right * nums[j] return answer这个版本的精妙之处在于第一轮遍历将answer数组变为左侧乘积第二轮从右向左遍历时用单个变量right动态维护右侧乘积省去了额外的存储空间除输出数组外4. 边界条件与特殊处理4.1 零值处理当数组包含0时需要特别注意单个0时除0位置外其他位置结果都为0多个0时所有位置结果都为0 但我们的解法天然正确处理了这些情况因为乘积计算会自然传播0值。4.2 大数溢出问题当数组元素值较大时乘积可能超出整型范围。在实际工程中需要使用Python无需担心自动大整数支持在Java/C等语言中可考虑取模运算如果题目允许添加中间结果检查5. 复杂度分析与对比解法类型时间复杂度空间复杂度适用场景暴力解法O(n²)O(1)绝对不可用标准前后缀数组O(n)O(n)教学理解优化空间版本O(n)O(1)不计输出面试最佳答案除法解法O(n)O(1)违反题目约束6. 变种问题拓展6.1 三维乘积问题如果要求计算除i,j位置外的所有元素乘积矩阵情况可以扩展思路计算每行的乘积数组row_product计算每列的乘积数组col_productanswer[i][j] row_product[i] * col_product[j] / nums[i][j]²6.2 乘积最大子数组类似思路可用于解决乘积最大子数组问题LeetCode 152通过同时维护当前最大值和最小值来应对负负得正的情况。7. 实际工程应用场景推荐系统计算特征权重时排除自身影响图像处理像素邻域运算时排除中心像素时间序列分析计算滑动窗口统计量时排除当前点金融分析计算投资组合风险时隔离单个资产影响8. 常见错误与调试技巧初始化错误忘记将answer[0]初始化为1后缀积遍历时right初始值设错索引越界处理空数组时直接访问nums[0]遍历时错用range范围调试建议# 打印中间结果 print(fStep {i}: left{left}, right{right}) # 使用断言检查 assert len(answer) len(nums)9. 不同语言实现要点9.1 Java实现注意// 注意数组初始化和类型声明 int[] answer new int[nums.length]; Arrays.fill(answer, 1);9.2 C优化技巧// 使用vector的assign方法快速初始化 vectorint answer(nums.size(), 1); // 反向遍历时注意size_t类型问题 for(int jnums.size()-2; j0; --j)10. 算法思维培养建议画图辅助绘制乘积关系示意图分治思想将问题分解为前缀和后缀两个子问题空间优化观察数据依赖关系寻找复用机会测试驱动先写测试用例再编码这个问题的精妙之处在于教会我们看似需要O(n²)时间的问题通过巧妙的预处理和空间换时间策略完全可以优化到线性时间复杂度。在实际工程中这种将复杂计算分解为多个线性扫描的模式类似MapReduce中的map阶段是非常有价值的思维模式。

相关推荐

Git远程协作全流程:从分支管理到冲突解决
Git远程协作全流程:从分支管理到冲突解决

1. 项目概述Git作为现代软件开发的核心工具,其远程协作能力直接决定了团队开发效率。在实际工作中,我发现很多开发者虽然能完成基础的代码提交,但遇到分支管理、冲突解决等复杂场景时往往手足无措。本文将基于我多年团队协作经验,… · 2026/11/5 7:12:37

STM32模拟IIC驱动PCF8563 RTC:时序实现与避坑指南
STM32模拟IIC驱动PCF8563 RTC:时序实现与避坑指南

简介:面向嵌入式开发者的 STM32 软件模拟 IIC 实践代码,聚焦用普通 GPIO 口线还原时序,完成对 PCF8563 时钟芯片的时间读写,可解决部分型号未集成硬件 IIC 模块时的读取需求,也可作为理解 IIC 协议时序与驱动分层写法的… · 2026/11/5 7:12:37

STM32模拟IIC读取PCF8563:时序、寄存器与避坑
STM32模拟IIC读取PCF8563:时序、寄存器与避坑

简介:面向使用STM32开展嵌入式时钟与RTC实验的初学者和工程人员,这套代码以普通GPIO模拟IIC总线时序,完成对低功耗实时时钟芯片PCF8563的读写控制。其价值在于绕开硬件IIC外设的型号差异,通过软件方式实现起始、停止、应答检测和字… · 2026/11/5 7:12:37

从 CSV 到图表:Pandas 数据处理与 Matplotlib 可视化上手实践
从 CSV 到图表:Pandas 数据处理与 Matplotlib 可视化上手实践

从 CSV 到图表:Pandas 数据处理与 Matplotlib 可视化上手实践 【免费下载链接】code_snippets 项目地址: https://gitcode.com/gh_mirrors/co/code_snippets 如果你从没写过数据分析代码,这篇教程给你一条最短路径:拿一份真实的 CSV … · 2026/11/5 7:45:49

Boring Notch 安装指南:3 步搞定未识别开发者弹窗
Boring Notch 安装指南:3 步搞定未识别开发者弹窗

Boring Notch 安装指南:3 步搞定未识别开发者弹窗 【免费下载链接】boring.notch TheBoringNotch: Not so boring notch That Rocks 🎸🎶 项目地址: https://gitcode.com/gh_mirrors/bor/boring.notch 刚下载完 Boring Notch&#xff… · 2026/11/5 7:45:49

CMAC算法的各种密码分析方法全面盘点
CMAC算法的各种密码分析方法全面盘点

CMAC算法的各种密码分析方法全面盘点对CMAC(基于密码的消息认证码)的密码分析,其攻击面已从传统的数学理论扩展到量子计算和具体实现等多个维度。以下是针对CMAC算法的各类密码分析方法全面盘点。📜 经典密码分析攻击这类攻击基于… · 2026/11/5 7:45:49

CRC-MAC算法的各种密码分析方法全面盘点
CRC-MAC算法的各种密码分析方法全面盘点

CRC-MAC算法的各种密码分析方法全面盘点将CRC(循环冗余校验)这种线性、非加密的校验和直接用作或改造为MAC(消息认证码),在密码学上是高度不安全的。其根本原因在于CRC的设计目标是检测随机传输错误,而非抵… · 2026/11/5 7:45:49

Linux --进程信号
Linux --进程信号

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 7:45:49

打印机SNMP被锁怎么办:epson_print_conf USB模式绕过新款爱普生打印机访问限制的实战指南
打印机SNMP被锁怎么办:epson_print_conf USB模式绕过新款爱普生打印机访问限制的实战指南

【免费下载链接】epson_print_conf Epson Printer Configuration tool and waste ink counter resetter 项目地址: https://gitcode.com/gh_mirrors/ep/epson_print_conf 点击查看 免费下载 新款爱普生(Epson)打印机把 SNMP 的 EEPROM 访问锁… · 2026/11/5 7:44:49

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码