互联网高频算法面试题-构建乘积数组
2023-03-15 21:59:03 时间
前言
大家好,我是来自于华为的程序员小熊。最近由于比较忙,好久没更新公众号了,不好意思。
今天带来一道与数组相关的面试高频题,这道题在半年内被字节、微软和亚马逊等互联网大厂作为面试题考过,即力扣上的第 238 题-除自身以外数组的乘积和剑指 Offer 66 题-构建乘积数组。
构建乘积数组
给定一个数组 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]。不能使用除法。
示例及提示
解题思路
本题最容易想到的方法:将数组元素都相乘,再将乘积除以原数组的每一个元素,即可得到构建后乘积数组中每个元素的值。
由于数组中的元素可能为 0,会有除 0 的风险,且本题要求不能使用除法,所以该方法不可行。
要求构建乘积数组后某下标对应元素的值,可以考虑分别求出该下标对应左边(不含该下标)元素的乘积和其右边的元素的乘积,最后将两个乘积再相乘即可。
举例
以 nums = [1,2,3,4]为例,如下图示。
例子
要求除下标为 2 以外的元素的积
求除下标为 2 以外的元素的积
先求下标为 2 左侧元素的乘积;
下标为 2 左侧元素的积
再求下标为 2 右侧元素的乘积(只有一个元素 4);
所以除下标为 2 以外的元素的积为左侧乘积 * 右侧乘积。
最终计算结果
nums = [1,2,3,4] 的完整求解过程,如下动图所示。
完整求解过程
Show me the Code
C
int* constructArr(int* a, int aSize, int* returnSize){
if (a == NULL || aSize < 2) {
*returnSize = 0;
return a;
}
int *res = (int *)malloc(aSize * sizeof(int));
if (res == NULL ) {
*returnSize = 0;
return res;
}
memset(res, 0, aSize * sizeof(int));
*returnSize = aSize;
/* 左侧乘积 */
for (int i = 0, product = 1; i < aSize; product *= a[i], i++) {
res[i] = product;
}
/* 左侧乘积乘以右侧乘积 */
for (int i = aSize - 1, product = 1; i >= 0; product *= a[i], i--) {
res[i] *= product;
}
return res;
}
C++
vector<int> constructArr(vector<int>& a) {
int len = a.size();
if (len == 0) {
return {};
}
vector<int> res(len, 1);
for (int i = 0, product = 1; i < len; product *= a[i], i++) {
res[i] = product;
}
for (int i = len - 1, product = 1; i >= 0; product *= a[i], i--) {
res[i] *= product;
}
return res;
}
Java
int[] constructArr(int[] a) {
int len = a.length;
int[] res = new int[len];
for (int i = 0, product = 1; i < len; product *= a[i], i++) {
res[i] = product;
}
for (int i = len - 1, product = 1; i >= 0; product *= a[i], i--) {
res[i] *= product;
}
return res;
}
复杂度分析
时间复杂度:O(n),其中 n 是数组的长度。
空间复杂度:O(1)。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十