LeetCode刷题MEDIM篇Product of Array Except Self

LeetCode刷题MEDIM篇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.)

十分钟尝试

本来第一反应，当前元素输出output值应该是全部的product除以当前元素，以为很完美可以处理，写完发现，忽略了一个0，如果有0我的代码不行，为了排除0，写了分支条件，还是不行。

class Solution {public int[] productExceptSelf(int[] nums) {int[] output=new int[nums.length];int allProduct=1;int allProductExceptZero=1;//如果有0不对for(int i=0;i<nums.length;i++){allProduct*=nums[i];}if(allProduct==0){//有0则，其他都是0，是0的位置不为0for(int k=0;k<nums.length;k++){if(nums[k]!=0){allProductExceptZero*=nums[k];output[k]=0;}}for(int m=0;m<nums.length;m++){if(nums[m]==0){output[m]=allProductExceptZero;}}return output;}for(int j=0;j<nums.length;j++){output[j]=allProduct/nums[j];}return output;}
}

正确解法

举例1 2 3 0 4，如果选择3，那么其实结果是左侧乘积*右侧乘积。所以第一层循环，计算截止到某个元素的累计乘积结果，右侧，再一次循环，最后一个元素就是1，第二个就是nums[j]，第三个right*=nums[j]，利用right表示右侧的累计乘积结果。所以代码如下：

class Solution {public int[] productExceptSelf(int[] nums) {int[] res=new int[nums.length];res[0]=1;for(int i=1;i<nums.length;i++){//注意，此处nums索引是i-1res[i]=res[i-1]*nums[i-1];}int right=1;for(int j=nums.length-1;j>=0;j--){res[j]*=right;right*=nums[j];}return res;}
}