题目描述

给定一个数组 A[0,1,...,n-1]，请构建一个数组 B[0,1,...,n-1]，其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。（注意：规定B[0] = A[1] A[2] ... A[n-1]，B[n-1] = A[0] A[1] ... A[n-2]）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

示例

输入：
[1,2,3,4,5]
返回值：
[120,60,40,30,24]

代码实现

时间复杂度：O(n^2)

/**
 * [暴力] 构建乘积数组
 *
 * @param A int整型一维数组
 * @return int整型一维数组
 */
func multiply(A []int) []int {
    n := len(A)
    B := make([]int, n)
    for i := 0; i < n; i++ {
        B[i] = 1;
        for j := 0; j < n; j++ {
            if i == j {
                continue
            }
            B[i] *= A[j]
        }
    }
    return B
}

优化方法

时间复杂度：O(n)

/**
 * 构建乘积数组
 *
 * @param A int整型一维数组
 * @return int整型一维数组
 */
func multiply(A []int) []int {
    n := len(A)
    letf := 1
    B := make([]int, n)
    for i, v := range A {
        B[i] = letf
        letf *= v
    }
    right := 1
    for j := n - 1; j >= 0; j-- {
        B[j] *= right
        right *= A[j]
    }
    return B
}