题目链接:https://leetcode.com/problems/product-of-array-except-self/
题目:
n integers where n > 1, nums
, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Solve it without division and in O(n).
[1,2,3,4]
, return [24,12,8,6]
.
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not
思路:
1、规避除法。用两个数组描述元素左、右边乘积,结果就是该元素左右乘积之积。空间复杂度为O(n)
2、在上述思路基础上减少数组的使用,用result代替右边的乘积,再用一个常数表示元素左边乘积。
算法1:
public int[] productExceptSelf(int[] nums) {
int right[] = new int[nums.length]; //元素右边乘积
int left[] = new int[nums.length];//
int result[] = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
if (i == nums.length - 1) {
right[i] = 1;
} else {
right[i] = right[i + 1] * nums[i + 1];
}
}
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
left[i] = 1;
} else {
left[i] = left[i - 1] * nums[i - 1];
}
}
for (int i = 0; i < nums.length; i++) {
result[i] = right[i] * left[i];
}
return result;
}
算法2:
public int[] productExceptSelf(int[] nums) {
int result[] = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) { //元素右边乘积
if (i == nums.length - 1) {
result[i] = 1;
} else {
result[i] = result[i + 1] * nums[i + 1];
}
}
int left = 0;//左边乘积
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
left = 1;
} else {
left= left * nums[i - 1];
result[i] = result[i] * left;
}
}
return result;
}