剑指offer—构建乘积数组

拼搏现实的明天。 2022-11-13 01:55 171阅读 0赞

**剑指offer题目描述：**

给定一个数组`A[0,1,...,n-1]`,请构建一个数组`B[0,1,...,n-1],`其中B中的元素`B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]`。不能使用除法。（注意：规定`B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]`）  
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在

示例1  
输入

[1,2,3,4,5]

返回值

[120,60,40,30,24]

--------------------

**解题思路1:**

由于连乘时需要回避掉当前数字，将数组遍历两次即可。其中，引入number变量的目的是为了弥补两次遍历数组这种方法的缺陷，**即**当数组中出现两次0的情况时\[1,2,0,3,0\]，结果可能无法为0的情况 \[0,0,6,0,6\] (错误)

--------------------

**代码1：**

class Solution:
        def multiply(self, A):
            # write code here
            B = []
            for i in range(len(A)):
                s = 1
                number = 1
                num = A[i]
                for j in range(len(A)):
                    if A[j] == num and number <= 1:
                        number += 1
                        continue
                    else:
                        s *= A[j]
                B.append(s)
            return B

--------------------

**解题思路2:** 来源于:[krahets][]

首先当计算 B \[ i \] B\[i\] B\[i\]时，对应的 A \[ i \] A\[i\] A\[i\]那一项相当于乘1。因此，这里给出的思路主要是先计算 A \[ i \] A\[i\] A\[i\]左侧的累积，然后再将其与 A \[ i \] A\[i\] A\[i\]右侧的累积相乘起来即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

**代码2：**

python代码：

class Solution:
        def constructArr(self, a):
            b, tmp = [1] * len(a), 1
            for i in range(1, len(a)):
                b[i] = b[i-1] * a[i-1]  # 下三角
            for i in range(len(a)-2, -1, -1):
                tmp *= a[i+1]  # 上三角
                b[i] *= tmp    # 下三角 * 上三角
            return b

java代码：

import java.util.ArrayList;
    public class Solution {
        
        public int[] multiply(int[] A) {
        
            if(A.length == 0) return new int[0];
            int[] b = new int[A.length];
            b[0] = 1;
            int tmp = 1;
            for(int i = 1; i < A.length; i++) {
        
                b[i] = b[i - 1] * A[i - 1];
            }
            for(int i = A.length - 2; i >= 0; i--) {
        
                tmp *= A[i + 1];
                b[i] *= tmp;
            }
            return b;
        }
    }

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/][https_leetcode-cn.com_problems_shu-zu-zhong-zhong-fu-de-shu-zi-lcof]

[krahets]: https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/ced6c383ca864fcebe35cc940915487b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/c7bd4912df0f4011b64fd1b4c36c670b.png
[https_leetcode-cn.com_problems_shu-zu-zhong-zhong-fu-de-shu-zi-lcof]: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/