- Product of Array Except Self
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
思考：不用除法,怎么实现 ? time O(n) space O(1)
/*
Wrong 我的方法1: 全部相乘，再除以当前元素。这样有个问题，如果当前为0，结果不对
*/
public int[] productExceptSelf_my(int[] nums) {
int[] res = new int[nums.length];
int sum = 1;
for(int item:nums){
if(item != 0){
sum *= item;
}
}
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0){
res[i] = sum;
}else{
res[i] = sum/nums[i];
}
}
return res;
}
/*
Right 答案方法: 先计算左侧 乘积left,再计算右侧乘积right; 结果 = left * right
o[i] = a[0]a[1]...a[i-1] * a[i+1]...a[n-1]
*/
public int[] productExceptSelf_solution(int[] nums) {
int[] res = new int[nums.length];
//初始化为1
for(int i = 0; i < nums.length; i++){
res[i] = 1;
}
//计算left数组
int left = 1;
for(int i = 1; i < nums.length;i++){
left = left * nums[i - 1];
res[i] = res[i] * left;
}
//计算right
int right = 1;
for(int i = nums.length - 2; i >= 0;i--){
right = right * nums[i+1];
res[i] = res[i] * right;
}
return res;
}
