题解 | #构建乘积数组#

构建乘积数组

http://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46

最容易想到的就是暴力法,依次求出每个B[i],但是这样的时间复杂度为O(n^2),效率太低了。
既然暴力法效率太低,那就看看能不能找出B[i]之间的关系来提高效率。

由上图可以发现

B[i]的左半部分(红色部分)和B[i-1]有关,将红色部分乘积和看成C[i],则有C[i] = C[i-1]*A[i-1]
B[i]的右半部分(紫色部分)和B[i+1]有关,可以使用一个temp代表B[i]的右半部分,每次temp*A[i+1]
 
因此我们可以先从0遍历到n-1,计算出B[i]的左半部分。然后将左半部分与代表其有半部分的temp相乘,即可得到B[i]。
数组间的关系通过画图更容易找出关系
import java.util.ArrayList; public class Solution {     public int[] multiply(int[] A) {         if(A == null)return null;         int length = A.length;         if(length == 0 || length == 1)return new int[0];         int[] B = new int[length];         B[0] = 1;         for(int i = 1;i < length;i++){             B[i] = B[i - 1] * A[i - 1];         }         int temp = 1;         for(int i = length - 2;i >= 0;i--){             temp *= A[i + 1];             B[i] *= temp;         }         return B;     } }

全部评论

相关推荐

昨天 21:28
已编辑
南京市金陵中学 C++
最后以华为13级这个并不那么满意的offer结束支离破碎的秋招。bg:本硕双9电子信息类,非计算机,论文只有一篇ei会议。秋招目标:私企(问就是亲眼所见国企关停)转码前:研一时虽然大部分师兄师姐在转码,但是各种渠道渲染我们的专业很强,当时的想法是不转码肯定能找到满意的私企,然后拿本科毕设投了个ei会议,并开始自己找课题研究(导师放养)。研一下找到方向,研二上在仿真和写论文的时候开始意识到形势不好,越来越多的学长学姐申请华为的对口职位流程挂或只有个别勉强拿到offer,在萌生转码的念头时论文写到一半,于是决定论文写完再转码,觉得论文对找工作有用(现在来看对找开发的工作作用聊胜于无)。论文写完已经是12月中旬,一次次找导师改收到的是一次次拖延,直到3月份一个字没改让我投顶刊我才意识到这一年半的努力在秋招时不可能再转化为成果了。一个408只学过计算机网络,语言只学过c++且期末也只是刚及格的牛马从12月底才开始了转码。转码:算法卷院校卷顶刊没戏,只可能转开发,由于很多学长学姐都转码拿到华为的offer,难度不高,所以我最开始的目标是通过c++技术栈拿下华为并尝试互联网后端。零基础一切都要现学,所以就先从数据结构、操作系统、算法题这些开发类必备的知识学起,寒假开始刷力扣,当时根本不算是刷题,全是在看题解,印象很深刻的是第一题两数之和折磨了我一下午。三月刷力扣+背408八股,到三月底听计算机的同学说暑期实习后端卷麻了,相反前端今年相对简单,经过几天的考虑,最终决定两线作战:前端和c++,此时认为华为能稳稳作为保底。四月9106匆忙学了html+css+js,五月学了vue就去投实习了,b站腾讯阿里国际美团滴滴给了面试,但只有美团到了终面,结果还因为过于紧张以及没经验说错了话,与offer失之交臂。五月剩下的时间为华为准备了一个c++开源项目,六七月学react并准备了一个前端项目。本来的梦想是秋招签阿里等华为,然而噩梦就要开始了。秋招:先说结论吧,眼高手低,互联网一个都没拿到,老本行拿到某雷达所,前端拿到体面厂和性价比厂,c++拿到某学历厂、华子外包、迪子和两个通信大厂,两个前端base一个杭州一个南京,总包都不到25,c++的几个里华子外包和迪子base深圳,另外三个base上海且薪资降序。八月九月上旬集中投递前端岗位,每天都在笔试测评,但给面试的只有美团京东淘天,美团终面面试官百般刁难,甚至拷打前端发展历史这种问题,寄了之后美团再没捞我,必然是脏了面评,京东一面hr面,拷打我本科成绩和无竞赛奖项,直接寄,淘天二面挂。然后九月中旬发现互联网希望渺茫,慢一步投递了c++相关岗位,华为线下面试一天速通池子后拒了研究所的oc,抱着华为稳了的想法准备结束秋招,结果几天后问面试情况被告知面评非3A。这最后一根稻草压垮了996半年的我,整日的emo和严重的焦虑导致我不停的胡思乱想,加上那几天我的室友和我同一时间投递的三家都有进展甚至oc而我没有任何进展,我在发呆焦虑迷茫中度过了那一周。而一周之后算是有些好消息,开始有offer了,至少不至于毕业即失业。为了给华为留一线生机拒了最早来的一家(听说华为不等这家毁约),体面厂在接受意向后,华为在经过一系列沟通后告知可以给offer,因此未签三方,性价比厂oc后紧接着收到华为通知报批通过,接着就是现在华为第一批开奖了。总结:看着现在同学没有杂七杂八想法单一技术栈allin华为oc14甚至15级很不甘心,回想起来我可能在每个节点都做错了选择:在研一时不做充分调研就对不转码找工作过于自信,不该在只有几个月时间准备的情况下开辟第二战场转前端,不该在找不到暑期实习后还继续梭哈前端,不该在互联网全线溃败时面试华为导致面试官觉得我不够自信……太多的错误导致了这个结局。看好华为的平台以及去上海的意愿让我最后做出了接受13级的选择。回顾这接近19年的学习阶段,我总是在尝试向上卷:中考和全市人竞争重点高中,高考和全省人竞争985,考研更是千军万马过独木桥。我卷进了重点高中,但是我的努力收获的是高三一次比一次差的成绩,高考我考了一个高三从未考到过的成绩,曾经我认为这才是我的真实水平,但是现在我觉得我错了,本科时我卷不过同学,花费几倍于别人的努力却只能勉强达到差不多的水平;考研初试我靠着接近一年的995才收获高分,而准备同样时间的复试我就远远落后于别人;花费同样的时间在科研上也不能获得与别人差不多的成果。曾经我也自命不凡,但我现在意识到自己就是个平凡到不能再平凡的人,我的努力在命运面前仿佛沧海一粟。借用自己很喜欢的一首歌的歌词来结尾吧:“难以释怀的&nbsp;让时间冲淡&nbsp;至少我还在期盼。”希望工作顺利,希望生活如意。
牛客220859485号:唉,加油吧老哥,硕士拿13已经很吃亏了。感觉老哥是选择做错了,卷一卷java去互联网后端没问题的,华子也不是只收c++。all in C++是把路走窄了。
点赞 评论 收藏
分享
评论
2
收藏
分享
牛客网
牛客企业服务