赞
踩
题目描述:
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/product-of-array-except-self
一个超时的算法:
时间复杂度为O(n2)
class Solution:
def productExceptSelf(self, nums):
output=[]
for i in range(len(nums)):
temp=1
if i+1==len(nums):
lst=nums[:i]
else:
lst=nums[:i]+nums[i+1:]
for j in lst:
temp*=j
output.append(temp)
return output
不超时的:
时间复杂度为O(2n)
class Solution: def productExceptSelf(self, nums): n=len(nums) output=[] for i in range(n): output.append(1) left=1 right=1 for i in range(n): output[i]*=left left*=nums[i] output[n-i-1]*=right right*=nums[n-1-i] return output
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。