剑指offer_构建乘积数组
2019-04-06 本文已影响0人
zhouwaiqiang
题目描述
给定一个数组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]。不能使用除法。
解题思路
- 这道题的含义是给定一个数组，然后需要构建一个数组其结果是数组对应的位置是给定数组除了对应位置数字以外的所有数的乘积，不允许采用除法（不然就可以所有相乘除以对应位置的数得到结果了）
- 可以将数据的乘法分为某个所求位置结果的左右两部分乘积，如下图中图1所示，假设需要求下标为2对应的结果，现在可以分为两部分，左边数值是1和2，右边数值是4，5那么只需要分别求得左边乘积结果和右边乘积结果就可以得到答案
- 那么针对每个位置都需要进行这样的操作，我们可以声明一个和这个原始数组一样大小的数组存储结果为result数组
- 首先我们考虑左乘，数组第一个数即是下标为0，此时左边是没有数据的，那么此时result[0]=1,表示左边没有数据(但是右边有数据，乘法乘以1不会改变结果，如果为0乘以0都是0没有意义)，此时我们再依次更新后面的数据根据以上的思路可以得出result[i]=num[i-1]*result[i-1]，这样就可以得到对应位置左边数的乘积
- 然后需要从右边高位开始着手将result的对应位结果乘以右边的数值，也可以再声明一个数组如法炮制得到右边乘法结果再两个数组对应位置相乘得到结果，但是这样空间损耗会增多
- 那么就用一个变量代替，只需要找到对应节点i的右侧的乘积乘以result[i]就可以得到最后的结果。做法如下，首先声明一个right变量为1，因为从数组高位开始，最高位右侧是没有数据的所以此时result[i]的结果就已经是最终结果，然后往前挪动的时候，需要将num[i]的结果乘积到right中得到右侧结果，下一次执行的时候在吧这个结果乘以result[i]得到相应的结果即可
解析步骤图片
图1初始化
图2左边乘积
图3右边乘积
java源代码
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
result[0] = 1;
int length = nums.length;
for (int i = 1; i < length; i++) {
result[i] = result[i-1] * nums[i-1];
}
int right = 1;
for (int i = length-1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}
}
