剑指Offer_51

发表于 | 分类于

题目

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0] x A[1]x … x A[i-1] x A[i+1] x … x A[n-1]。不能使用除法。

解题思路

举个例子

1
2
3
4
5
B0：X A1 A2 A3 A4
B1：A0 X A2 A3 A4
B2：A0 A1 X A3 A4
B3：A0 A1 A2 X A4
B4：A0 A1 A2 A3 X

两趟循环，第一趟处理对角线的左下角，第二趟处理对角线的右上角。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
    	int []B = new int[A.length];
        
        B[0] = 1;
        for(int i = 1; i < A.length; ++i){
            B[i] = A[i-1] * B[i-1];
        }
        
        int temp = 1;
        for(int i = A.length-1; i >= 0; --i){
            B[i] *= temp;
            temp *= A[i];
        }
        
        return B;
    }
}