Given an array of n integers where n > 1, nums, return an array output such that outputi is equal to the product of all the elements of nums except numsi.
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.)
可以定义两个辅助数组,left和right。
lefti:存放numsi之前的乘积
righti:存放numsi之后的乘积
但是分析一下,空间可以优化,因为我们先从右向左算,再从左向右算,只需要返回的那一个数组就够了。
public int[] productExceptSelf(int[] nums) {
int[] rt = new int[nums.length];
rt[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
rt[i] = rt[i + 1] * nums[i+1];
}
int left = 1;
for (int i = 0; i < nums.length; i++) {
rt[i] *= left;
left *= nums[i];
}
return rt;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。