力扣 - 剑指 Offer 66. 构建乘积数组

2021年6月24日 5点热度 0条评论 来源: linzeliang

题目

剑指 Offer 66. 构建乘积数组

思路1

  • 按照一般的思路就是将所有的相乘,然后除以每一位数字就是答案,但是题目要求我们不能使用除法,因此我们会想到每次遍历到每个数字的时候,在遍历一遍数组,将除开自己以外的数字相乘,但是这样做的时间复杂度确是\(O(N^2)\),导致超时,因此我们需要想另外一种方法来解决

  • 根据题意,我们可以知道B[i]=A[0]*A[1]*A[2]*...*A[i-1]*A[i+1]*...*A[n-1],所以我们以i为分界线,将这个拆成两部分,所以B[i]就等于A[0]*...*A[i-1]A[i+1]*...*A[n-1]的乘积,所以数组B可以看作用一个矩阵来创建。我们以[1, 2, 3, 4]为例,如图所示:

    可以看出,对角线是都为1。然后从第二行开始,我们先计算下三角的每一行的乘积:B[i] = B[i-1] * A[i-1]

    从倒数第二行开始,再从下往上计算上结果:B[i] *= A[i+1],因为左边部分已经计算出来了,所以直接拿来乘就可以了

代码

class Solution {
    public int[] constructArr(int[] a) {
        int length = a.length;

        if (length == 0) {
            return new int[0];
        }
        int[] arr = new int[length];

        // 先构建左下三角形
        arr[0] = 1;
        for (int i = 1; i < length; i++) {
            arr[i] = arr[i-1] * a[i-1];
        }
        // 构建右上三角形同时计算结果
        int temp = 1;
        // 从倒数第二个开始往前
        for (int i = length-2; i >= 0; i--) {
            temp *= a[i+1];
            arr[i] *= temp;
        }

        return arr;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(1)\)
    原文作者:linzeliang
    原文地址: https://www.cnblogs.com/linzeliang1222/p/15506440.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。