1. 不可用除法，最容易的方法全部乘积除不可用了。
2. 后路想到，使用两个数组，分别乘积，左边数组的前半截和右边数组的后半截乘积即可。o(n);
3. 压缩空间，那么直接使用output来承接left，使用原数组承接right，即可(画图，即可发现)。
第一种方法代码：
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int leftList[] = new int[length];
int rightList[] = new int[length];
int output[] = new int[length];
leftList[0] = nums[0];
rightList[length-1] = nums[length-1];
for(int i = 1; i < length; i++){
leftList[i] = leftList[i-1]*nums[i];
}
for(int i = length-2; i >= 0; i--){
rightList[i] = rightList[i+1]*nums[i];
}
for(int i = 0; i < length; i++){
int left = i-1>=0 ? leftList[i-1]:1;
int right = i+1<length?rightList[i+1]:1;
output[i] = left*right;
}
return output;
}
}
第二种方法代码：
class Solution {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int output[] = new int[length];
output[0] = nums[0];
for(int i = 1; i < length; i++){
output[i] = output[i-1]*nums[i];
}
for(int i = length-2; i >= 0; i--){
nums[i] = nums[i+1]*nums[i];
}
int left;
int right;
for(int i = 0; i < length; i++){
left = i-1>=0 ? output[i-1]:1;
right = i+1<length?nums[i+1]:1;
nums[i] = left*right;
}
return nums;
}
}
网友评论