Product of Array Except Self

问题：

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饒瑞泓