首页 > 代码库 > [LintCode] Product of Array Except Self 除本身之外的数组之积
[LintCode] Product of Array Except Self 除本身之外的数组之积
Given an integers array A.
Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.
Have you met this question in a real interview?
Yes
Example
For A = [1, 2, 3], return [6, 3, 2].
LeetCode上的原题，请参见我之前的博客Product of Array Except Self。
解法一：
class Solution {public: /** * @param A: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { int n = nums.size(); vector<long long> fwd(n, 1), bwd(n, 1), res(n); for (int i = 0; i < n - 1; ++i) { fwd[i + 1] = fwd[i] * nums[i]; } for (int i = n - 1; i > 0; --i) { bwd[i - 1] = bwd[i] * nums[i]; } for (int i = 0; i < n; ++i) { res[i] = fwd[i] * bwd[i]; } return res; }};
解法二：
class Solution {public: /** * @param A: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { long long n = nums.size(), right = 1; vector<long long> res(n, 1); for (int i = 1; i < n; ++i) { res[i] = res[i - 1] * nums[i - 1]; } for (int i = n - 1; i >= 0; --i) { res[i] *= right; right *= nums[i]; } return res; }};
[LintCode] Product of Array Except Self 除本身之外的数组之积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。