Q:
Given an integers array A.
Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.
Example
For A = [1, 2, 3], return [6, 3, 2].
Code:
思路很简单，第一遍算前n-1项累计的乘积，第一项是1，第二项是n(0)，第二项是n(0)n(1)，第n项是1n(0)n(1)...n(n-2)n(n-1)，第二遍算后n-1项累计的乘积，再和前n-1项相乘，恰好可以错开一位，例如：（下面的数字都是在nums中的项数）
ans0: 1x2x3x...xn (全是第二遍的乘积)
ans1: 0x2x3x4x...xn(第一项是第一遍的乘积，后面2-n是第二遍的积）
ans2: 0x1x3x4x...xn（0和1是第一遍的乘积，后面3-n是第二遍的乘积）
......
ans n-1 :0x1x2x...xn-2xn（0到n-2是第一遍乘积，n是第二遍乘积）
ans n: 0x1x2...xn-2 x n-1（全是第一遍乘积）
还有一种解法，形式不太容易看出来，
思路一样，先算后n-1项累计的乘积，再用temp和now的乘积计算前n-1项乘积，用now*f[i+1] 错一位相乘。
网友评论