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

程序员小熊

发布于 2021-11-18 11:22:26

25700

代码可运行

文章被收录于专栏：程序员小熊带你学算法程序员小熊带你学算法

运行总次数：0

代码可运行

前言

大家好，我是来自于华为的程序员小熊。最近由于比较忙，好久没更新公众号了，不好意思。

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

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 删除

编程算法

本文分享自程序员小熊微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度