互联网高频算法面试题-构建乘积数组

会员服务 ·

互联网高频算法面试题-构建乘积数组

2021 年 11 月 24 日 极市平台

↑ 点击蓝字关注极市平台

作者丨Dine

来源丨程序员小熊

编辑丨极市平台

极市导读

今天带来一道与数组相关的面试高频题，这道题在半年内被字节、微软和亚马逊等互联网大厂作为面试题考过，即力扣上的第 238 题-除自身以外数组的乘积和剑指 Offer 66 题-构建乘积数组。 >>加入极市CV技术交流群，走在计算机视觉的最前沿

前言

今天带来一道与数组相关的面试高频题，这道题在半年内被字节、微软和亚马逊等互联网大厂作为面试题考过，即力扣上的第 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 右侧元素的乘积（只有一个元素 4）；

所以除下标为 2 以外的元素的积为左侧乘积 * 右侧乘积。

nums = [1,2,3,4] 的完整求解过程，如下动图所示。

Show me the Code

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;  

}