欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 09:16:56
...

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%的用户
  • 算法说明:
    用一次遍历求出对应的值,从左向右求出左积,从右向左求出右积,返回结果。