[leetcode] 238. Product of Array Except Self

[leetcode] 238. Product of Array Except Self

Description

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.)

分析

题目的意思是：计算数组中除本身之外的乘积。

对于某一数字，如果我们知道其前面所有数字的乘积，同时也知道后面所有的乘积，那么二者就是我们要的结果。因此我们创建一个数组来保存前面连乘的结果，前向遍历一次，后向遍历一次就行了。

代码

class Solution {public: vector productExceptSelf(vector& nums) { vector result(nums.size(),1); for(int i=1;i=0;i--){ result[i]=right*result[i]; right=right*nums[i]; } return result; }};

参考文献

​​[LeetCode] Product of Array Except Self 除本身之外的数组之积​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。