题解 | #构建乘积数组#
构建乘积数组
http://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46
描述
给定一个数组 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]（除 A[i] 以外的全部元素的的乘积）。
程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]）
对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。
示例1
输入：[1,2,3,4,5]
返回值：[120,60,40,30,24]
示例2
输入：[100,50] 返回值：[50,100]
解法：置1法
- 定义双层循环 i j
- 由题意知道，当前元素A[ i ] 不参与乘积，所以可以把它置为1
- 然后跳过A[j] 即 i==j 时不做处理
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
// 1. 构建返回的数组
int [] res = new int[A.length];
// 2. 遍历
for (int i = 0; i < A.length; i++) {
// 3.当前元素置为1
res[i]=1;
for (int j = 0; j < A.length; j++)
// 4. i!=j 时候，构建乘积
if (i != j) {
res[i] = res[i] * A[j];
}
}
return res;
}
}
查看11道真题和解析
