# Product of Array Except Self
Date: 2024-01-08


#### **问题：**

Given an array arr\[\] of n integers, construct a Product Array prod\[\] (of the same size) such that prod\[i\] is equal to the product of all the elements of arr\[\] except arr\[i\].

#### **解答:**

遍历数组循环跳过当前元素，需要两层循环， 时间复杂度O(n^2),空间复杂度O(n)

```
def arrayOfProducts(array):
    products = [1 for _ in range(len(array))]
    for i in range(len(array)):
        runningProduct = 1
        for j in range(len(array)):
            if i != j:
                runningProduct = runningProduct * array[j]
            products[i] = runningProduct
    return products
```

 

使用两个临时数组，一个数组存放从左边到i个元素的积， 另外一个从右边开始到第i个元素的积。然后两个结果相乘放到结果集。

```
def arrayOfProducts(array):
    # Write your code here.
    products = [1 for _ in range(len(array))]
    leftProducts = [1 for _ in range(len(array))]
    rightProducts = [1 for _ in range(len(array))]

    leftRunningProduct = 1
    for i in range(len(array)):
        leftProducts[i] = leftRunningProduct
        leftRunningProduct *= array[i]
        
    rightRunningProduct = 1
    for i in reversed(range(len(array))):
        rightProducts[i] = rightRunningProduct
        rightRunningProduct *= array[i]
        
    for i in range(len(array)):
        products[i] = leftProducts[i] * rightProducts[i]

    return products
```

使用一个临时数组，直接放到结果集中。

```
def arrayOfProducts(array):
    # Write your reversecode here.
    products = [1 for _ in range(len(array))]

    leftRunningProduct = 1
    for i in range(len(array)):
        products[i] = leftRunningProduct
        leftRunningProduct *= array[i]
        
    rightRunningProduct = 1
    for i in reversed(range(len(array))):
        products[i] *= rightRunningProduct
        rightRunningProduct *= array[i]
        
    return products

```

 

#### **参考及引用：**

https://www.algoexpert.io/questions/array-of-products

图片 白頭鶇，台灣特有種 from[**饒瑞泓**](https://www.facebook.com/groups/296994820448873/user/100003745412806/?__cft__[0]=AZUEmStDVL8cBJcZwYvRld-Qfx_nosIHcHqFxAlINmk2dKeOtklMKQGK0W2oGGsbkoIV1gLbYclNwghFVMd1UAnKAaCdXzQuxLc3kMa3hrvBwXoNF424tUcqwZcraxTkNG5lJTutciy7FKuRihdO9L8hsBxDQx_OlOL7NNBpVq6Fw-pWk02xC5_QfNYubRHQJhQ&__tn__=-UC%2CP-R)