【剑指OFFER】66. 构建乘积数组
发布日期:2021-06-29 19:47:24
浏览次数:2
分类:技术文章
本文共 1034 字,大约阅读时间需要 3 分钟。
题目:给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]提示:
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000答案:
class Solution { public int[] constructArr(int[] a) { //从头到尾,把前i项相乘放在b中,再从尾到头,把缺失的补上去 if(a.length == 0 || a.length == 1) return a; int[] b = new int[a.length]; b[0] = 1; int c = 1; for(int i = 1; i < a.length; i++){ c *= a[i - 1]; b[i] = c; } c = 1; for(int i = a.length - 2; i >= 0; i--){ c *= a[i + 1]; b[i] *= c; } return b; }}
优化后:
class Solution { public int[] constructArr(int[] a) { //从头到尾,把前i项相乘放在b中,再从尾到头,把缺失的补上去 int[] b = new int[a.length]; for(int i = 0, c = 1; i < a.length; c *= a[i], i++){ b[i] = c; } for(int i = a.length - 1,c = 1; i >= 0; c *= a[i], i--){ b[i] *= c; } return b; }}
转载地址:https://darkness.blog.csdn.net/article/details/116237003 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月30日 03时04分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SDL arm linux平台交叉编译(好文章已测试)
2019-04-30
linux 常用查看设备命令
2019-04-30
Linux内核及文件系统配置编译 - 关于内核配置
2019-04-30
android应用前期开发之经验总结
2019-04-30
Linux 下zip包的压缩与解压
2019-04-30
Andoird SDK目录解析
2019-04-30
Google Guava官方教程(中文版)
2019-04-30
Guava教程
2019-04-30
The Book of QT4 翻译:1.2 布局,对象层级和内存管理
2019-04-30
麒麟信安UniKylin3.3安装配置pyqt5运行环境
2019-04-30
linux中python3 pip快速搭建pyqt5环境
2019-04-30
泛型程序设计
2019-04-30
Java集合
2019-04-30
Java List集合
2019-04-30
Java Set集合 HashSet TreeSet
2019-04-30
Java Map集合
2019-04-30
ASCII、ISO-8859-1和GB系列编码
2019-04-30
Unicode及UTF-8、UTF-16、UTF-32
2019-04-30
UCS-2、UCS-4
2019-04-30
Unicode和UCS
2019-04-30