238. Product of Array Except Self（python+cpp）-白红宇

238. Product of Array Except Self（python+cpp）

阅读量：3702 次

发布时间：2019-05-21

本文共 1334 字，大约阅读时间需要 4 分钟。

题目：

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input:  [1,2,3,4] Output: [24,12,8,6]
Note:
Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

解释：’

我们以一个4个元素的数组为例，nums=[a1, a2, a3, a4]。

想在O(n)时间复杂度完成最终的数组输出，res=[a2*a3*a4, a1*a3*a4, a1*a2*a4, a2*a3*a4]。

比较好的解决方法是构造两个数组相乘：

[1, a1, a1*a2, a1*a2*a3]===>list_a

[a2*a3*a4, a3*a4, a4, 1]

python代码：

class Solution(object):    def productExceptSelf(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        n=len(nums)        p=1        list_a=[1]*n        for i in range(n):            list_a[i]=p            p=p*nums[i]        p=1        for i in range(n-1,-1,-1):            list_a[i]*=p            p=p*nums[i]        return list_a

c++代码：

class Solution {
   public:    vector
   
     productExceptSelf(vector
    
     & nums) {
           int n=nums.size();        vector
     
      a_list(n,1);        int p=1;        for (int i=0;i
      
       =0;i--)        {
               a_list[i]*=p;            p*=nums[i];        }        return a_list;    }};