【Java】 剑指offer(66) 构建乘积数组
2024-04-02 13:05:43
本文参考自《剑指offer》一书，代码采用Java语言。
题目
给定一个数组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)，效率非常低。
考虑到计算每个B[i]时都会有重复，思考B[i]之间的联系，找出规律，提高效率。
图片转自构建乘积数组
如上图所示，可以发现：
B[i]的左半部分(红色部分)和B[i-1]有关（将B[i]的左半部分乘积看成C[i]，有C[i]=C[i-1]*A[i-1]），
B[i]的右半部分(紫色部分)与B[i+1]有关（将B[i]的右半部分乘积看成D[i]，有D[i]=D[i+1]*A[i+1]），
因此我们先从0到n-1遍历，计算每个B[i]的左半部分； 然后定义一个变量temp代表右半部分的乘积，从n-1到0遍历，令B[i]*=temp，而每次的temp与上次的temp关系即为temp*=A[i+1]。
测试代码
1.功能测试（正、负、零）
2.边界值测试（数组长度为2）
3.特殊测试（null，数组长度为1，0）
Java代码
//题目：给定一个数组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]。不能使用除法。 public class ConstuctArray {
public int[] multiply(int[] A) {
if(A==null || A.length<2)
return null;
int[] B=new int[A.length];
B[0]=1;
for(int i=1;i<A.length;i++)
B[i]=B[i-1]*A[i-1];
int temp=1;
for(int i=A.length-2;i>=0;i--){
temp*=A[i+1];
B[i]*=temp;
}
return B;
}
}
收获
1.考虑到了数组B中的元素间有关系，要进一步分析。本题就是采用画图的方法，将B看成一个矩阵，就能轻易地看出元素之间的关系了。好好学习。
2.可以直接从头到尾再从尾到头遍历，不需要创建两个临时数组C[]和D[]。自己写代码时，要尽量设计不用创建太多内存空间。
3.如果这道题可以用除法的话，记得除数不能为零！
最新文章
- IIS短文件名暴力枚举漏洞利用脚本
- phpunit测试学习 1：一点简单的扼要有用的东西的总结 一点入门认识
- art虚拟机启动问题分析
- hdu 4006 The kth great number(优先队列)
- python 连接sql server
- Python for Informatics 第11章 正则表达式二（译）
- #nav li:hover ul 与#nav li a:hover ul 的区别
- anr产生的原理&如何避免(android)
- android 图片叠加效果——两种方法
- form表单中的enctype属性什么意思？
- new jQuery.common
- Java设计模式03：常用设计模式之单例模式（创建型模式）
- uva 123 Searching Quickly
- Cooley-Tukey算法 （蝶形算法）
- 一位同学3年通过CPA, CFA, ACCA的经验
- 车牌识别OCR—易泊时代智慧城市解决方案模块
- SqlParameter 用法总结
- python类与对象-如何为创建大量实例节省内存
- linux audit审计（2）--audit启动
- JS实现控制HTML5背景音乐播放暂停