《剑指offer》第六十六题：构建乘积数组

2021-02-17 21:17

阅读：403

标签：初始 cst product 个数 put style bsp 构建二维

// 面试题66：构建乘积数组
// 题目：给定一个数组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]。不能使用除法。

#include 
#include using namespace std;
//把B[i]看成[=A[0],A[1],… ,A[i-1],1,A[i+1],…,A[n-1]]
//对于B，就成了二维数组，对于1左面是上三角矩阵，右面是下三角矩阵
//三角矩阵的每行乘积值计算可以从顶向下
void BuildProductionArray(const vectordouble>& input, vectordouble>& output)
{
    int length1 = input.size();
    int length2 = output.size();

    if (length1 == length2 && length2 > 1)
    {
        output[0] = 1;
        for (int i = 1; i i)
        {
            output[i] = output[i - 1] * input[i - 1];//计算左面上三角矩阵的每行乘积值
        }

        double temp = 1;
        for (int i = length1 - 2; i >= 0; --i)//注意两个循环的i初始化值
        {
            temp *= input[i + 1];//计算下三角矩阵的每行乘积值
            output[i] *= temp;//上下三角的同行乘机值再相乘，就是满足题意的B[i]值了
        }
    }
}

标签：初始 cst product 个数 put style bsp 构建二维

原文地址：https://www.cnblogs.com/ZSY-blog/p/12695113.html

上一篇：python

下一篇：Python数据分析之Numpy入门

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《剑指offer》第六十六题：构建乘积数组
文章链接：http://soscw.com/index.php/essay/56740.html

亲，登录后才可以留言！

《剑指offer》第六十六题：构建乘积数组

评论

热门文章

推荐文章

最新文章

置顶文章