题目描述
给定一个数组 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]。不能使用除法。
思路
代码
import Strategy.Strategy;
import java.lang.reflect.Array;
import java.util.Arrays;
public class MultiArr {public static void main(String[] args){MultiArr multiArr = new MultiArr();
int[] a = {1, 2, 3,4,5};
// int[] a = {1,2};
/*int[] a = {1, 2, 3,4,5,6};
int[] a = {1, 2, 3,4,5,6};*/
int[] multiply = multiArr.multiply(a);
System.out.println(Arrays.toString(multiply));
}
public int[] multiply(int[] A) {
// 注意特殊 case
if(A.length == 0 || A == null)return A;
if(A.length == 1) return A;
int len = A.length;
int[] B = new int[len];
int[] C = new int[len];
// 设置数组 C 和 D 的初始值
C[0] = 1;
C[1] = A[0];
int[] D = new int[len];
D[len - 1] = 1;
D[len - 2] = A[len - 1];
// 需要注意的就是两个 for 循环的边界条件
for(int i = 1; i < len - 1; i++){C[i + 1] = C[i] * A[i];
}
for(int i = len - 2; i >= 0; i--){D[i] = D[i+1] * A[i+1];
}
for(int i = 0; i < len; i++){B[i] = C[i] * D[i];
}
return B;
}
}