首页 > 编程语言 > 详细

除自身以外数组乘积

时间:2021-09-01 14:07:27      阅读:16      评论:0      收藏:0      [点我收藏+]

此博客链接:

除自身以外数组乘积

题目链接:https://leetcode-cn.com/problems/product-of-array-except-self/

题目

给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

 

示例:

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

提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。

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

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

题解

这道题如果每次算除自身以外的数组乘积,需要遍历n*(n-1)次,时间复杂度应该相当高,但是如果我们只比阿尼一次数组求出所以数组的乘积,然后算除自身的数组元素乘积时,可以用全部数组的乘积除以自身,这样只需要遍历一次,就求出结果了。

代码

结果

除自身以外数组乘积

原文:https://www.cnblogs.com/ping2yingshi/p/15206607.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!