【刷算法】构建乘积数组

yuanxin 发布于2019-08-23 10:30 / 2678人阅读

摘要：题目描述给定一个数组请构建一个数组其中中的元素。分析设结果数组为，给定数组为，首先取再取，，，至此，数组正确构造完毕。

题目描述

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

分析

设结果数组为res，给定数组为arr=[a,b,c,d]，首先取：

res[0] = 1

res[1] = res[0]*arr[0] = a

res[2] = res[1]*arr[1] = ab

res[3] = res[2]*arr[2] = abc

再取temp = arr[4] = d

res[2] = res[2]temp = abd，temp = temparr[2] = cd

res[1] = res[1]temp = acd，temp = temparr[1] = bcd

res[0] = res[0]temp = bcd，temp = temparr[0] = abcd

至此，res数组正确构造完毕。

代码实现

function multiply(arr)
{
    var res = [], index = 1;
    res[0] = 1;
    
    for(var i = 0;i < arr.length-1;i++) {
        res[index] = res[index-1] * arr[i];
        index++;
    }
    
    var temp = arr[arr.length-1], index = res.length-2;
    for(var i = arr.length-2;i >= 0;i--) {
        res[i] *= temp;
        temp *= arr[index--];
    }
    
    return res;
}

混合云私有云 php数组之间乘积数组中求乘积 json 构建数组最大堆构建算法举例

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96405.html

【刷算法】和为S的两个数字

摘要：题目描述输入一个递增排序的数组和一个数字，在数组中查找两个数，是的他们的和正好是，如果有多对数字的和等于，输出两个数的乘积最小的。解题思路数组是递增的，且给的数字是固定的，那就可以用夹逼法。和碰头了说明该结束了。题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。解题思路数组是递增的，且给的数字...

Dr_Noooo 2019-08-22 18:14 评论0 收藏0
❤️思维导图整理大厂面试高频数组19: 股票问题III的dp数组构建/初始化和空间优化难点, 力扣1

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...

刘福 2021-10-11 10:59 评论0 收藏0
漫谈 | “黎曼猜想”和区块链加密算法到底有什么关系？

摘要：假如黎曼猜想被证实，区块链将毁灭近日，黎曼猜想四个字疯狂刷屏。黎曼猜想由数学家波恩哈德黎曼于年提出。因此，黎曼猜想一旦被证明，则意味着素数之密被解开，算法也就将被攻破了。而大多数区块链所用的加密算法不是，而是椭圆曲线加密算法。玛丽女王的密码之生死命悬一线 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世纪伊丽...

tracymac7 2019-06-27 18:47 评论0 收藏0