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.)
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
A:
从前向后走一遍,计算之前的乘积再从后向前走一遍,计算之后的乘积,
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> res(n,1); // two round, forward, and backward for(int i =1;i<n;++i) res[i] = res[i-1] * nums[i-1]; int back = 1; for(int i = n-1; i>=0; --i) { res[i] *= back; back *= nums[i]; } return res; } };
用2个帮助数组
public class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int pre[] = new int[n]; int after[] = new int[n]; pre[0] = 1; for(int i =1;i<n;i++) pre[i] = pre[i-1]*nums[i-1]; after[n-1] = 1; for(int i=n-2;i>=0;i--) after[i] = after[i+1] * nums[i+1]; int[] result = new int[n]; for(int i =0;i<n;i++) result[i] = pre[i] * after[i]; return result; } }
Follow up:
为节省空间,用result数组和给的nums数组代替pre after 数组。
public class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] pre = new int[n]; pre[0] = 1; for(int i =1;i<n;i++) pre[i] = pre[i-1]*nums[i-1]; for(int i=n-2;i>0;i--) nums[i] = nums[i+1] * nums[i]; for(int i =0;i<n-1;i++) pre[i] = pre[i] * nums[i+1]; return pre; } }
Mistakes:
No comments:
Post a Comment