面试题66. 构建乘积数组/238. 除自身以外数组的乘积(一般)

给定一个数组 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]。不能使用除法。

示例:

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

思路：

算法流程：

  • 初始化：数组 B ，其中 B[0] = 1；辅助变量 tmp=1 ；
  • 计算 B[i] 的 下三角 各元素的乘积，直接乘入 B[i] ；
  • 计算 B[i] 的 上三角 各元素的乘积，记为 tmp ，并乘入 B[i] ；
  • 返回 B 。

作者：jyd
链接：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/

回看记录200726

添加代码2，是leetcode238的代码，这两题一模一样

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] constructArr(int[] a) {
        if(a.length==0 || a==null)
            return new int[0];
        int[] b = new int[a.length];
        b[0]=1;
        for(int i=1;i<a.length;i++){
            b[i]=b[i-1]*a[i-1];
        }
        int tmp =1;
        for(int i=a.length-2;i>=0;i--){
            tmp *= a[i+1];
            b[i] *= tmp;
        }
        return b;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] constructArr(int[] nums) {
        //以当前书，分左右两边，然后左右撑起来就是当前位置的输出值
        int len = nums.length;
        int[] res = new int[len];
        if(len==0)
            return res;   
        int[] left = new int[len];
        int[] right = new int[len];
        
        left[0]=1;
        for(int i=1;i<len;i++){
            left[i]=nums[i-1]*left[i-1];
        }
        right[len-1]=1;
        for(int i =len-2;i>=0;i--){
            right[i]=nums[i+1]*right[i+1];
        }

        for(int i=0;i<len;i++){
            res[i]=left[i]*right[i];
        }
        return res;
    }
}