剑指 Offer 66: 构建乘积数组

[songyy5517]

给定一个数组 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]

分析 通过分析 $B[0]$ 到 $B[n-1]$ 的计算过程，我们可以发现 $i$ 左右两端的乘积是有规律的。左边是 $1 \times A[0] \times A[1] \times ... \times A[i-1]$ ，右边是 $1\times A[n-1] \times A[n-2] \times ... \times A[i+1]$ 。因此，我们可以先单独计算这两个部分的乘积，然后将它们再乘积即可得到B数组。

[songyy5517]

思路：乘积分解，将乘积分解成上三角和下三角，分别迭代计算两部分。

1. 异常处理；
2. 定义两个数组 $preprod$ 和 $postprod$ 分别存放前后乘积；（代码空间优化：只用一个数组。）
3. 自下而上计算前乘积数组，自上而下计算后乘积数组；
4. 两数组对应元素相乘即可得到最终结果。

复杂度分析

• 时间复杂度： $O(N)$ ， $N$ 为数组长度，计算上下三角乘积使用了 $O(N)$ 时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量，前乘积数组 $preprod$ $O(N)$ 为必要返回空间，因此不计入算法的空间复杂度。

[songyy5517]

class Solution {
    public int[] productExceptSelf(int[] a) {
        // 思路：分解成乘积矩阵
        // 1. 异常处理
        if (a == null || a.length == 0)
            return new int[0];

        // 2. 定义前后乘积数组
        int[] pre_prod = new int[a.length];  // a[0]*...*a[i-1]
        int post_prod = 1;
        pre_prod[0] = 1;

        // 3. 自下而上求前乘积数组
        for (int i = 1; i < a.length; i++)
            pre_prod[i] = pre_prod[i-1] * a[i-1];

        // 3. 自下而上求后乘积数组 & 计算最终结果
        for (int i = a.length - 1; i >= 0; i--){
            pre_prod[i] *= post_prod;
            post_prod *= a[i];
        }

        return pre_prod;
    }
}

[songyy5517]

2023/11/25 2024/5/9

• 238. Product of Array Except Self