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

除自身以外数组的乘积

除自身以外数组的乘积

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

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

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

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示:

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

题解:

​ 思路主要是,当前节点的除了自身以外的数的乘积,可以理解为当前节点左边所有数和右边所有数字的乘积,这样呢有点像 leetcode 接雨水的问题,我们可以同时用两个数组来存储左边所有数字的乘积和右边所有数字的乘积,这样对应节点的乘积就是答案;当然了,如果我们想进一步优化空间复杂度,可以使用两个指针,一边移动一遍乘积(方法二)

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] left = new int[n];int[] right = new int[n];left[0] = 1;for (int i = 1; i < n; i++) {left[i] = nums[i - 1] * left[i - 1];}right[n - 1] = 1;for (int i = n - 2; i >= 0; i--) {right[i] = nums[i + 1] * right[i + 1];}int[] ans = new int[n];for (int i = 0; i < n; i++) {ans[i] = left[i] * right[i];}return ans;}
}
func productExceptSelf(nums []int) (ans []int) {n := len(nums)ans = make([]int, n)lp, rp := 1, 1for i := range ans {ans[i] = 1}for l,r := 0,n-1; l < n && r >=0; l, r = l+1, r-1 {ans[l] *= lpans[r] *= rplp *= nums[l]rp *= nums[r] }return
}

http://www.mrgr.cn/news/75177.html

相关文章:

  • 【 ElementUI 组件Steps 步骤条使用新手详细教程】
  • 细说STM32单片机USART中断收发RTC实时时间并改善其鲁棒性的另一种方法
  • Redis8:商户查询缓存2
  • 图像处理实验三(Morphological Image Processing)
  • git config 保存密码
  • 基于vue框架的的商品销售平台p2l5b(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
  • 关于GCC内联汇编(也可以叫内嵌汇编)的简单学习
  • 共享旅游卡项目深度解读,风险与机遇并存
  • Java 常见的面试题(Kafka)
  • 三天精通一种算法之移除数组元素(暴力)(快慢指针)
  • MySQL数据库:SQL语言入门 【2】(学习笔记)
  • Spring Security概述
  • 基于树莓派的日志抓取工具制作
  • 代理通讯链实现内网通讯
  • 探秘 RPC:揭开远程过程调用的实现原理
  • 如何在python中模拟重载初始化函数?
  • 下载|阿里云等联合编写的《2024大模型典型示范应用案例集》发布
  • 「Mac玩转仓颉内测版10」PTA刷题篇1 - L1-001 Hello World
  • Jdbc学习笔记(四)--PreparedStatement对象、sql攻击(安全问题)
  • 联丰策略炒股股票交易市场券商股,盘中突然拉升
  • 25京考考试时间已确定,速速查收!
  • 时序论文19|ICML24 : 一篇很好的时序模型轻量化文章,用1k参数进行长时预测
  • Linux系统编程多线程之条件变量和信号量讲解
  • java八股-垃圾回收机制-垃圾回收算法,分代回收,垃圾回收器
  • 精灵图(十八课)
  • RHCE web解析、dns配置、firewalld配置实验