·题目描述
·解题思路:
————————时间换空间(for循环暴力求解)————————
1.两个for循环不断乘积
2.稍作优化——先判断是否有0存在,若是在乘积的余下数组中有0直接判断为0 (但是只是最优时间复杂度减少,没什么大作用)
代码:
class Solution(object):def productExceptSelf(self, nums):#牺牲时间换空间n = len(nums)res = [0] * nfor i in range(n):multiply = 1if 0 in nums[:i] or 0 in nums[i+1:]:multiply = 0for j in range(n):if j == i:multiply *= 1else:multiply *= nums[j]res[i] = multiplyreturn res
————————牺牲空间换时间(两个额外数组空间,记录前缀积和后缀积)——————
1.利用pre数组记录每个元素的前缀积,pre[0]= 1 (图解如下,来源力扣官网)
2.利用post数组记录后缀积,post[-1]= 1 (图解)
3.将pre和post两个数组对应元素相乘所得数据就是最后的结果,直接放到nums原始数组的对应位置上,即可
代码:
def productExceptSelf(self, nums):#牺牲空间换时间n = len(nums)pre ,post = [0] * n, [0] * npre[0] , post[n-1] = 1 , 1for i in range(n-1):pre[i + 1] = nums[i] * pre[i]for j in range(n-1 , 0 , -1):post[j - 1] = post [j] * nums[j]for i in range(n):nums[i] = pre[i] * post [i]return nums
—————————兼顾时间和空间————————
1.将两个数组pre和post压缩为一个数组result
2.先用result记录原始的前缀积,步骤同上
3.利用动态字母R,记录后缀积。因为每个元素的前缀积已经记录,后缀积不断从后往前移动并且相乘更新R的值即可
(同样的思路,也可以先用resul记录后缀积,动态字母L记录前缀积,L从前往后移动即可)
代码:
def productExceptSelf(self, nums):##兼顾时间和空间n = len(nums)result = [0] * nresult[0] = 1for i in range(n-1):result[i+1] = nums[i] * result[i]R = 1for j in range(n-1, -1,-1):result[j] = result[j] * RR *= nums[j]return result