Problem:
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.)
Solution: DP
Time complexity: O(n)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 36 ms class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { const int n = nums.size(); vector<int> l(n, 1); // l[i] = prod(nums[0] ~ nums[i - 1]) vector<int> r(n, 1); // l[i] = prod(nums[i + 1] ~ nums[n - 1]) vector<int> ans(n); for (int i = 1; i < n; ++i) l[i] = l[i - 1] * nums[i - 1]; for (int i = n - 2; i >= 0; --i) r[i] = r[i + 1] * nums[i + 1]; for (int i = 0; i < n; ++i) ans[i] = l[i] * r[i]; return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 32 ms class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { const int n = nums.size(); int l = 1; // l = prod(nums[0] ~ nums[i - 1]) int r = 1; // r = prod(nums[i + 1] ~ nums[n - 1]) vector<int> ans(n, 1); for (int i = 0; i < n; ++i) { ans[i] *= l; ans[n - i - 1] *= r; l *= nums[i]; r *= nums[n - i - 1]; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment