首页 > 代码库 > LeetCode Q238 Product of Array Except Self(Medium)

LeetCode Q238 Product of Array Except Self(Medium)

Product of Array Except Self

原题:

Given an array of 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).

For example, given [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 count as extra space for the purpose of space complexity analysis.)

翻译:

给定一个整型数组nums(元素数量大于1),返回一个数组output,其中output[i]等于nums中除nums[i]的所有元素的乘积。ps:你可以在不使用除法和其他辅助空间的情况下通过吗?(储存返回的结果的变量不算)

分析:
解法一:
  朴素算法,首先计算所有元素的积product,再算出output[i]=product/nums[i](注意product为0时或nums中只有一个0时要特殊处理),这样空间复杂度为O(1)。但这明显违反题目要求:不能用除法。
解法二:
  那么可以保存nums[i]左右两边的乘积,然后再相乘。假设nums左边0至i个元素相乘为left[i],右边i至nums.Length的乘积为right[i],output[i]=left[i-1]*right[i+1]。辅助空间为O(2n),仍然违反题目要求。
解法三:
  再观察一下解法二,其实right可以直接存在output中,然后再从遍历整个数组,当遍历到output[i]时(i>0),left*=nums[i-1],就这样不停地更新left。时间复杂度为O(n),空间复杂度为O(1)。
 1 public class Solution  2 { 3     public int[] ProductExceptSelf(int[] nums)  4     { 5         int[] output = new int[nums.Length]; 6         output[output.Length-1] = 1; 7         for(int i=output.Length-2; i>=0; i--)  8         { 9             output[i] = output[i+1] * output[i+1];10         }11         int left = 1;12         for(int i=0; i<nums.Length; i++) 13         {14             output[i] *= left;15             left *= nums[i];16         }17         return output;18     }19 }

  又一个完美的Accepted Solutions。

LeetCode Q238 Product of Array Except Self(Medium)