剑指Offer——构建乘积数组

发布时间:2017-7-9 7:18:42编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"剑指Offer——构建乘积数组 ",主要涉及到剑指Offer——构建乘积数组 方面的内容,对于剑指Offer——构建乘积数组 感兴趣的同学可以参考一下。

Question

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

Solution

  • 不能用除法,那么我们可以考虑构建除去A[i] 的左右两部分的乘积,也就是0 ~ i-1 和 i+1到n-1.

  • 对应相乘就是去掉A[i]项的结果,也就是B[i]的结果

  • 时间复杂度O(n)

Code

class Solution {public:    vector<int> multiply(const vector<int>& A) {        if (A.size() == 0)            return vector<int>();                vector<int> res1(A.size() + 1);        res1[0] = 1;  // 构造开始项        for (int i = 1; i < A.size(); i++) {            res1[i] = res1[i - 1] * A[i - 1];        }                vector<int> res2(A.size() + 1);        res2[A.size()] = 1;  //构造结束项        for (int j = A.size() - 1; j >= 1; j--) {            res2[j] = A[j] * res2[j + 1];        }                vector<int> res(A.size());        for (int i = 0; i < A.size(); i++) {            res[i] = res1[i] * res2[i + 1];        }


上一篇:【翻译自mos文章】在12c数据库中,哪种audit trail 受到支持?
下一篇:HDU 5489 二分 LIS

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款