238. Product of Array Except Self (Medium)
https://leetcode.com/problems/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).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
Solutions
class Solution {
// Calculate the left production from head to specific element.
// Calculate the right production from tail to specific element.
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] ans = new int[len];
ans[0] = 1;
for (int i = 1; i < len; i++) {
// Update ans[i] to assign the production of values before i to it.
ans[i] = ans[i - 1] * nums[i - 1];
}
// ans[len-1] has already sorted out.
// right production after i
int rp = 1;
for (int i = len - 2; i >= 0; i--) {
// right production after i
rp = rp * nums[i + 1];
// Since ans[i] already contains the production of values before i, we are
// expected to multiply the production of right side elements so that we can
// gain the desired production.
ans[i] = ans[i] * rp;
}
return ans;
}
}
2.
class Solution {
// Problem requires solution without division, but this is also a good solution.
// Take care of situations that elements contain zeros
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] ans = new int[len];
Arrays.fill(ans, 0);
int fullProd = 1;
int zeroNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
zeroNum++;
continue;
}
fullProd *= nums[i];
}
// 1. >= 2 zeros, all the production should be 0
if (zeroNum >= 2) {
return ans;
}
// 2. 1 zero, all the production should be 0 except ith element which is of 0 value
if (zeroNum == 1) {
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
continue;
}
ans[i] = fullProd;
return ans;
}
}
// 3. 0 zero, normal situation
for (int i = 0; i < nums.length; i++) {
ans[i] = fullProd / nums[i];
}
return ans;
}
}