互联网高频算法面试题-构建乘积数组
前言
大家好，我是来自于华为的程序员小熊。最近由于比较忙，好久没更新公众号了，不好意思。
今天带来一道与数组相关的面试高频题，这道题在半年内被字节、微软和亚马逊等互联网大厂作为面试题考过，即力扣上的第 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)。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-11-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录