微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 66. 构建乘积数组

剑指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]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

  • 所有元素乘积之和不会溢出 32 位整数
  • a.length <= 100000

题解

(前后缀分解,模拟) O(n)

对于每一个数的结果都可以分成两部分的乘积，左边所有数的乘积 * 右边所有数的乘积

  1. 从前往后遍历数组，使用一个临时变量 p 记录当前位置前的所有数的乘积，同时记录此时的结果 res[i]
  2. 从后往前遍历数组，使用一个临时变量 p 记录当前位置后的所有数的乘积，将 p * res[i] 就是当前位置左右两部分乘积的结果。

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> res(a.size());
        for (int i = 0, p = 1; i < a.size(); i ++ ) {
            res[i] = p;
            p *= a[i];
        }
        
        for (int i = a.size() - 1, p = 1; i >= 0; i -- ) {
            res[i] *= p;
            p *= a[i];
        }

        return res;
    }
};

Java 代码

class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        
        // 第一次遍历，计算每个元素左边所有元素的乘积
        for (int i = 0, product = 1; i < n; i ++ ) {
            res[i] = product;  // 将左边乘积赋值到 res 数组
            product *= a[i];   // 计算当前元素的乘积，以备下一个元素使用
        }
        
        // 第二次遍历，计算每个元素右边所有元素的乘积，并乘以之前的左边乘积
        for (int i = n - 1, product = 1; i >= 0; i -- ) {
            res[i] *= product;  // 将右边乘积与之前的左边乘积相乘，得到最终结果
            product *= a[i];    // 计算右边乘积，以备下一个元素使用
        }
        
        return res;
    }
}

Python 代码

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        n = len(a)
        res = [0] * n
        
        # 第一次遍历，计算每个元素左边所有元素的乘积
        product = 1
        for i in range(n):
            res[i] = product  # 将左边乘积赋值到 res 列表
            product *= a[i]   # 计算当前元素的乘积，以备下一个元素使用
        
        # 第二次遍历，计算每个元素右边所有元素的乘积，并乘以之前的左边乘积
        product = 1
        for i in range(n - 1, -1, -1):
            res[i] *= product  # 将右边乘积与之前的左边乘积相乘，得到最终结果
            product *= a[i]    # 计算右边乘积，以备下一个元素使用
        
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer