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.)
题目大意：
得到数组中每个元素除了本身，其它元素的乘积。
解法：
题目中有说在O(n)时间复杂度解出，并且不使用除法。但我只能想出使用除法的解法。
java：
class Solution {
public int[] productExceptSelf(int[] nums) {
int multi=1;
int []res=new int[nums.length];
int numOfZero=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0) numOfZero++;
else multi*=nums[i];
}
if (numOfZero==0) {
for (int i = 0; i < nums.length; i++) {
res[i] = multi / nums[i];
}
}else if (numOfZero==1){
for (int i = 0; i < nums.length; i++) {
if (nums[i]==0) res[i]=multi;
else res[i]=0;
}
}
return res;
}
}
优化过后的解法：
先将数组中每个数从最左边到这个数乘一遍，再从最右边到这个数乘一遍，得到的结果即可返回，而且是O(n)的时间复杂度，并没有使用到除法。
class Solution {
public int[] productExceptSelf(int[] nums) {
int []res=new int[nums.length];
res[0]=1;
for (int i=1;i<nums.length;i++){
res[i]=res[i-1]*nums[i-1];
}
int right=1;
for (int i=nums.length-1;i>=0;i--){
res[i]*=right;
right*=nums[i];
}
return res;
}
}
leetcode [238]Product of Array Except Self
原文：https://www.cnblogs.com/xiaobaituyun/p/10833629.html