【刷算法】构建乘积数组

简介: 【刷算法】构建乘积数组

题目描述


给定一个数组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;
}



相关文章
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
73 0
|
4月前
|
存储 机器学习/深度学习 监控
公司电脑上网监控中滑动窗口算法的理论构建与工程实现
本文提出一种基于滑动窗口算法的实时网络流量监控框架,旨在强化企业信息安全防护体系。系统采用分层架构设计,包含数据采集、处理与分析决策三大模块,通过 Java 实现核心功能。利用滑动窗口技术动态分析流量模式,结合阈值检测与机器学习模型识别异常行为。实验表明,该方案在保证高检测准确率的同时支持大规模并发处理,为企业数字化转型提供可靠保障。
92 0
|
7月前
|
JavaScript 算法 前端开发
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
12月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
109 0
|
7月前
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
91 7
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
286 23
|
11月前
|
机器学习/深度学习 算法 Python
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。本文详细介绍了随机森林的工作原理、性能优势、影响因素及调优方法,并提供了Python实现示例。适用于分类、回归及特征选择等多种应用场景。
579 7
|
12月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
178 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
11月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
421 0
|
12月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
129 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列

热门文章

最新文章