剑指offer——构建乘积数组_乘积数组 剑指offer c++-程序员宅基地

技术标签: 剑指offer  C++  

转自https://blog.csdn.net/quzhongxin/article/details/47183965

 

题目描述

给定一个数组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]。不能使用除法。

 

 时间复杂度O(n^2)的解法

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        int len = A.size();
        if(len < 1) return result;
        for(int i = 0; i < len; i++)
        {
            int temp = 1;
            for(int j = 0; j < len; j++)
            {
                if(j == i) continue;
                temp *= A[j];
            }
            result.push_back(temp);
        }
        return result;
    }
};

如果可以使用除法,那还可以每次乘一个数,除以一个数,以降低时间复杂度。

 

时间复杂度O(n),空间复杂度O(n)的解法

使用一个数组,保存元素组某位置 i 前的所有元素的乘积,另外一个数组,保存 i 后所有元素的乘积,

最后这两个数组相乘。

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        int len = A.size();
        if(len < 1) return result;
        int* C = new int[len];
        int* D = new int[len];
        C[0] = 1;
        D[len-1] = 1;
        for(int i = 1; i < len; i++)
        {
            C[i] = C[i - 1] * A[i - 1];
            D[len - 1 - i] = D[len - i] * A[len - i];
        }
        for(int i = 0; i < len; i++)
        {
            int temp = C[i] * D[i];
            result.push_back(temp);
        }
        return result;
    }
};

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Eartha1995/article/details/81507364

智能推荐

amos 结构方程模型无法运行出来-程序员宅基地

上面是画出来的结构模型,下面是运行的结果,显示出来是unidentified,请问是模型错了吗,还是数据问题。

modelsim 相关-程序员宅基地

勾掉 enable optimization 选项, 点ok。

win环境nginx配置网站403小记_windows11 nginx403-程序员宅基地

昨天在同事的电脑上我的项目修改host,nginx.conf完毕,cmd 进入nginx目录nginx stopstart nginx打开自己配的server_name403为什么?先查看配置文件确定没有问题然后检查一下文件权限(win下的权限,特么感觉就像不存在,不然怎么会有那么多全家桶)。也没问题不明白,再关掉nginx 发现还是403.。。什么鬼,不应_windows11 nginx403

结构方程模型如何分析?_结构方程模型数据造假_spssau的博客-程序员宅基地

结构方程模型是被广泛认可的研究可观测变量与潜在变量,以及潜在变量之间关系的重要工具。结构方程模型包括两个基本模型,分别为测量模型和结构模型,测量模型由潜在变量、观测变量以及测量误差项组成,主要分析潜在变量与观测变量的共变效果。路径分析在于研究模型影响关系,用于对模型假设进行验证。比如下图的模型框架:希望研究工作条件,人际关系对于公司满意度的影响;同时还希望研究公司满意度和机会感知对于离职倾向的影响。路径有一共有4条(即4对影响关系),路径分析可以同时研究此4对影响关系。_结构方程模型数据造假

什么是熔断、降级、限流_服务的熔断,限流降级分别是什么_呆萌很的博客-程序员宅基地

A服务调用B服务的某个功能,由于网络不稳定问题,或者B服务卡机,导致功能时间超长。如果这样子的次数太多。我们。我们就可以直接将B断路(A不再请求B接口),凡是调用B的直接返回降级数据,不必等待B的超长执行。这样B的故障问题,就不会级联影响到A。整个网站处于流量高峰期,服务器压力剧增,根据当前业务情况及流量,对一些服务和页面进行有策略的降级停止服务,所有的调用直接返回降级数据。以次缓解服务器资源的压力,以保证核心业务的正常运行,同时也保持大部分客户的得到正确的响应。_服务的熔断,限流降级分别是什么

Transformer及其在low-level vision中的应用_先验知识 transformer_JimmyCM的博客-程序员宅基地

Transformer是最近比较火的深度学习模型,它抛弃了传统的CNN和RNN,提出了一种全新的模型架构。借助于新的模型和大规模数据训练,transformer刷新了NLP和CV许多领域的指标,成为这些领域新的SOTA,大有要统一NLP和CV模型的趋势。当然,transformer本身也有许多解释性问题和缺点在被广泛研究改进,但不得不承认这是目前受到关注最多的模型之一了。基于最近看到的一些论文,本文对Transformer的主要观点和在视觉领域,特别是low-level视觉领域的发展做一个简单的总结。_先验知识 transformer

随便推点

Ensp中USG6000v登录解决办法_usg6000v一直井号解决方法_网络工程师新学徒的博客-程序员宅基地

一、解决前准备Ensp100版本、VirtualBox 5.2.44版本、USG600v导入包、VMware Workstation Pro15二、问题分析1、如果说USG600v打开一直####号,那应该是导入包没导成功,或者VirtualBox出现问题。2、如果说USG600v能正常打开,也能正常使用,连接云也没问题,但是只要传数据就会导致USG崩溃。应该是云的配置有问题。三、问题解决1、第一种情况直接重新导入即可。2、USG传数据崩溃,云的问题。在这张图片中,._usg6000v一直井号解决方法

bootstrap提供了六种列表效果_bootstrap 列表-程序员宅基地

列表--简介在HTML文档中,列表结构主要有三种:有序列表、无序列表和定义列表。具体使用的标签说明如下:无序列表 …有序列表 …定义列表 … …Bootstrap根据平时的使用情形提供了六种形式的列表: 普通列表 有序列表 去点列表 内联列表 描_bootstrap 列表

server id-程序员宅基地

一个MySQL集群中,绝不可以出现相同server_id的实例,否则各种诡异的问题可是接踵而来。slave 的server id 也不能相同

Echarts雷达图搭配极坐标_echarts雷达图设置刻度线-程序员宅基地

雷达图搭配极坐标项目搭建: vue + element UI + Echarts需求背景:利用Echarts的雷达图展示骑手配送的时间节点,需求效果图如下:鼠标hover至拐点的时候,展示相关的信息,移出的时候不显示采用原因:1:本项目采用的是Echarts 4.x,Echarts2.x以上的雷达图,tooltip触发方式设置成axis无效,而且设置成item的话,tooltip会包含所有数据,不能获取单个拐点的数据。2:Echart4.x 雷达图的刻度不再生效,也就是说没有刻度显示。_echarts雷达图设置刻度线

浮点数编程易出现错误_怎么把结构体浮点型变量老是在过程中报错-程序员宅基地

进行浮点数编程时,如果没有注意,常常会出现输出类似 1.#IND, 1.#INF 或者 nan, inf 之类奇怪的输出。这通常隐含了浮点数操作的异常。特殊浮点数的含义1.#INF / inf:这个值表示“无穷大 (infinity 的缩写)”,即超出了计算机可以表示的浮点数的最大范围(或者说超过了 double 类型的最大值)。例如,当用 0 除一个整数时便会得到一个1.#INF / i_怎么把结构体浮点型变量老是在过程中报错

Py之ipython:Python库之ipython的简介、安装、使用方法详细攻略-程序员宅基地

ipython是一个python的交互式shell,比默认的pythonshell好用得多,支持变量自动补全,自动缩进,支持bashshell命令,内置了许多很有用的功能和函数。学习ipython将会让我们以一种更高的效率来使用python。同时它也是利用Python进行科学计算和交互可视化的一个最佳的平台。IPython提供了两个主要的组件一个强大的python交互式shell;供Jupyternotebooks使用的一个Jupyter内核(IPythonnotebook)。..._ipython