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

LeetCode Q238 Product of Array Except Self(Medium)

2024-08-15 15:56:43   218人阅读

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)


联系
我们