Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output* is equal to the product of all the elements of nums except nums*.
Solve it without division and in O(n).
For example, given , return .
我们创建一个长度和原数组num长度一样的数组result,先从左边开始,让result = 1; result = 1 * num, result = num * num, result = num * num ...num。然后从右边开始,让result = result * 1; result = num * result; result = num * num .... num * result。这样遍历两遍数组就可以得到结果,代码如下:
public class Solution {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
int left = 1;
result[0] = 1;
for(int i = 1; i < nums.length; i++) {
result[i] = left * nums[i - 1];
left *= nums[i - 1];
}
int right = 1;
for(int j = nums.length - 1; j >= 0; j--) {
result[j] *= right;
right *= nums[j];
}
return result;
}
}