LeetCode刷题之238.除自身以外数组的乘积

LeetCode刷题之238.除自身以外数组的乘积

我不知道将去向何方，但我已在路上！

时光匆匆，虽未曾谋面，却相遇于斯，实在是莫大的缘分，感谢您的到访 ！

• 题目：
  给定长度为n的整数数组nums，其中n>1，返回输出数组output，其中output[i]等于nums中除nums[i]之外其余各元素的乘积。
• 示例：

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

• 说明：
  请不要使用除法，且在O(n) 时间复杂度内完成此题。链表中所有节点的值都是唯一的。
• 进阶：
  你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。)
• 代码1：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_val,right_val = [1]*len(nums),[1]*len(nums)
        result = []
        for i in range(1,len(nums)):
            left_val[i] *= left_val[i-1] * nums[i-1]
        for i in range(len(nums)-2,-1,-1):
            right_val[i] *= right_val[i+1] * nums[i+1]
        for i in range(len(nums)):
            result.append(left_val[i] * right_val[i])
        return(result)
# 执行用时 :152 ms, 在所有 Python3 提交中击败了79.30%的用户
# 内存消耗 :20.8 MB, 在所有 Python3 提交中击败了12.02%的用户

• 算法说明：
  第一个for循环，求出当前元素的左积；第二个for循环，求出当前元素的右积；第三个for循环，求出相同位置的左积元素和右积元素的乘积。
• 代码2：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1] * len(nums)
        left,right = 1,1
        for i in range(0,len(nums)):
            result[i] *= left
            left *= nums[i]
            result[len(nums)-i-1] *= right
            right *= nums[len(nums)-i-1]
        return(result)
# 执行用时 :216 ms, 在所有 Python3 提交中击败了27.78%的用户
# 内存消耗 :20.4 MB, 在所有 Python3 提交中击败了84.13%的用户

• 算法说明：
  用一次遍历求出对应的值，从左向右求出左积，从右向左求出右积，返回结果。