Jianbo Dai's

jz066.构建乘积数组

 
  • Oct 21, 2020

题目链接

对于所求B[i] = A[0] x A[1] x … x A[i-1] x A[i+1] x … x A[n-1]，我们可以将其看成C[i] = A[0] x A[1] x … x A[i-1] 和 D[i] = A[i+1] x … x A[n-1]两部分的乘积，对于C和D我们可以用循环依次计算出来。这个算法的时间复杂度是O（N），空间复杂度是O（N）。第二种是别人的实现，比较巧妙地节省了空间，并且由于b这个数组作为返回值不计入空间复杂度的计算（？），所以空间复杂为O（1）。

class Solution:
    def constructArr1(self, a: List[int]) -> List[int]:
        C, D = [1], [1]
        lena = len(a)
        for i in range(lena-1):
            C.append(C[i] * a[i])
            D.append(D[i] * a[lena-i-1])
        return [C[i]*D[lena-i-1] for i in range(lena)]

    def constructArr2(self, a: List[int]) -> List[int]:
        b, tmp = [1] * len(a), 1
        for i in range(1, len(a)):
            b[i] = b[i - 1] * a[i - 1] # 下三角
        for i in range(len(a) - 2, -1, -1): 
            tmp *= a[i + 1] # 上三角
            b[i] *= tmp # 下三角 * 上三角
        return b
Search