[剑指Offer]66-构建乘积数组
2024-10-09 20:30:23
题目
给定一个数组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]。不能使用除法。
题解
- 把数组B想象成用矩阵构建,B[i]为矩阵中第i行所有元素乘积,构建befI和afterI数组,B[i]=befI[i]*afterI[i]。
- 构建befI afterI数组分别自上而下和自下而上,时间复杂度O(n).
- 总体时间复杂度O(n).
代码
public class Main {
public static void main(String[] args) {
int[] A= {1,2,3,4,5};
int[] B=multiply(A);
for(int num:B) {
System.out.println(num);
}
}
public static int[] multiply(int[] A) {
int len=A.length;
int[] B=new int[len];
int[] befI=new int[len];
int[] afterI=new int[len];
befI[0]=1;
afterI[len-1]=1;
for(int i=1;i<len;++i) {
befI[i]=befI[i-1]*A[i-1];
}
for(int i=len-2;i>=0;--i) {
afterI[i]=afterI[i+1]*A[i+1];
}
for(int i=0;i<len;++i) {
B[i]=befI[i]*afterI[i];
}
return B;
}
}
最新文章
- 一个login
- STL数组处理常用函数
- HTML锁定Table中某一列
- Vert.x入门体验
- 关于gcd函数解最大公约数
- UITbaleView上按钮的单选
- 【Android车载系统 News | Tech 1】News 谷歌开发车载Android系统 2014-12-19
- LPSTR、LPCSTR、LPWSTR、LPCWSTR、LPTSTR、LPCTSTR的来源及意义
- Centos 6.4 安装elasticsearch+kibana
- js观察者模式
- 如何查看MySQL中每张表占用的空间大小
- C/C++ 指针的非空判断
- WPF制作的一个小功能,智能提示(IntelliSense)
- linux exec和文件描述符妙用技巧(转)
- Docker contanier comunication with route
- error=11, Resource temporarily unavailable
- 移动端响应式布局+rem+calc()
- [DeeplearningAI笔记]ML strategy_2_3迁移学习/多任务学习
- 告别 hash 路由,迎接 history 路由
- Python成长之路【第四篇】模块儿
热门文章
- CPF 入门教程 - 数据绑定和命令绑定(二)
- 编写高质量代码的50条黄金守则-Day 02(首选readonly而不是const)
- 【原创】Linux虚拟化KVM-Qemu分析(一)
- 实体类转xml
- Nmap在实战中的高级用法(详解)
- 在.NET Core中使用MongoDB明细教程(3):Skip, Sort, Limit, Projections
- 正规式转化为DFA
- Python方法oslo_service.loopingcall.LoopingCallDone代码示例
- linux下udev和mdev的使用
- CSS动画实例:行星和卫星