当前位置: 首页 > news >正文

代码训练LeetCode(24)数组乘积

代码训练(24)LeetCode之数组乘积

Author: Once Day Date: 2025年6月5日

漫漫长路,才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

  • 238. 除自身以外数组的乘积 - 力扣(LeetCode)
  • 力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

      • 代码训练(24)LeetCode之数组乘积
        • 1. 原题
        • 2. 分析
        • 3. 代码实现
        • 4. 总结

1. 原题

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法,**且在 O(n) 时间复杂度内完成此题。

提示:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 输入 保证 数组 answer[i]32 位 整数范围内

示例:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
2. 分析

我们需要计算一个数组 answer,其中每个元素 answer[i] 是原数组 nums 中除了 nums[i] 之外所有元素的乘积。关键点是我们不能使用除法,并且需要在 O(n) 时间复杂度内解决,同时尽量减少额外空间的使用。

题目提供了一个数组 nums,要求我们为每一个元素计算出它所有其他元素的乘积。使用除法的话会非常直接,但题目要求我们不能使用除法,因此我们需要找到其他方法。由于每个元素的结果是其他元素的乘积,我们可以将问题分解为两部分的乘积:当前元素左侧的所有元素的乘积和右侧所有元素的乘积。

解题思路

  1. 构建左积数组 L,其中 L[i] 表示 nums[i] 左侧所有元素的乘积。
  2. 构建右积数组 R,其中 R[i] 表示 nums[i] 右侧所有元素的乘积。
  3. 计算结果数组 answer,其中 answer[i] = L[i] * R[i]

分析步骤

构建左积数组

  • 初始化 L[0] = 1(因为第一个元素左边没有元素)。
  • 从左到右遍历 nums,每个 L[i] = L[i - 1] * nums[i - 1]

构建右积数组

  • 初始化 R[n-1] = 1(因为最后一个元素右边没有元素)。
  • 从右到左遍历 nums,每个 R[i] = R[i + 1] * nums[i + 1]

计算结果数组

  • answer[i] = L[i] * R[i]

举例分析,以示例 nums = [1,2,3,4]

构建 L:

  • L[0] = 1
  • L[1] = 1 (L[0] * nums[0])
  • L[2] = 2 (L[1] * nums[1])
  • L[3] = 6 (L[2] * nums[2])

构建 R

  • R[3] = 1
  • R[2] = 4 (R[3] * nums[3])
  • R[1] = 12 (R[2] * nums[2])
  • R[0] = 24 (R[1] * nums[1])

结果 answer:

  • answer[0] = L[0] * R[0] = 1 * 24 = 24
  • answer[1] = L[1] * R[1] = 1 * 12 = 12
  • answer[2] = L[2] * R[2] = 2 * 4 = 8
  • answer[3] = L[3] * R[3] = 6 * 1 = 6

性能优化关键点

  • 时间复杂度:O(n)。我们只需要三次遍历整个数组。
  • 空间复杂度:可以优化到 O(1)(不包括输出数组)。我们可以直接在输出数组上构建 L,然后用一个变量来跟踪右边元素的乘积。
3. 代码实现
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int i;*returnSize = numsSize;int *returnArray = malloc(numsSize * sizeof(int));// Build the answer array as left product arrayreturnArray[0] = 1;for (i = 1; i < numsSize; i++) {returnArray[i] = returnArray[i - 1] * nums[i - 1];}// Modify the answer array by multiplying with right productsint right = 1;for (i = numsSize - 1; i >= 0; i--) {returnArray[i] = returnArray[i] * right;right *= nums[i];}return returnArray;
}
4. 总结

这道题测试了对数组操作和优化的理解。通过空间复杂度优化,我们学习了如何利用已有的资源(输出数组和变量)减少空间需求。要提升编程能力,关键在于练习如何将问题分解成小的部分,并高效地解决它们。此外,学习如何通过一些小技巧(如变量跟踪)在有限的资源下完成任务也是很重要的。

http://www.lqws.cn/news/158131.html

相关文章:

  • day028-Shell自动化编程-判断进阶
  • 验证电机理论与性能:电机试验平板提升测试效率
  • 用 n8n 提取静态网页内容:从 HTTP Request 到 HTML 节点全解析
  • 【HarmonyOS 5】 影视与直播详以及 开发案例
  • Qt多线程访问同一个数据库源码分享(基于Sqlite实现)
  • 一次Oracle的非正常关闭
  • 十八、【用户认证篇】安全第一步:基于 JWT 的前后端分离认证方案
  • Cursor 1.0 版本 GitHub MCP 全面指南:从安装到工作流增强
  • oracle数据恢复—oracle数据库执行truncate命令后的怎么恢复数据?
  • 大疆相关知识收集
  • 深度解码:我如何用“结构进化型交互学习方法”与AI共舞,从学习小白到构建复杂认知体系
  • 从 ClickHouse、Druid、Kylin 到 Doris:网易云音乐 PB 级实时分析平台降本增效
  • 短视频矩阵系统技术saas源头6年开发构架
  • 【SSM】SpringMVC学习笔记7:前后端数据传输协议和异常处理
  • 05【Linux经典命令】Linux 用户管理全面指南:从基础到高级操作
  • Hive中ORC存储格式的优化方法
  • 服务器CPU被WMI Provider Host系统进程占用过高,导致系统偶尔卡顿的排查处理方案
  • 26考研 | 王道 | 计算机组成原理 | 四、指令系统
  • [蓝桥杯]堆的计数
  • 第14节 Node.js 全局对象
  • 华为云CentOS配置在线yum源,连接公网后,逐步复制粘贴,看好自己对应的版本即可,【新手必看】
  • 《中国电信运营商骨干网:历史、现状与未来演进》系列 第三篇:双网驱动的联通:从南北分家到CUBE-Net的融合创新
  • Java 异步编程难题及拆解技术
  • STL——栈和队列和优先队列
  • 谐波在线监测装置功能
  • Java八股文——集合「Queue篇」
  • LangchainRAG you need - 段落拆分
  • 欧拉公式简明推导
  • 【Android基础回顾】七:内存管理机制
  • 2025.5.28【33OJ NOI 模拟赛 T3】字符串(AC自动机, 字符串后缀结构)