剑指Offer(57)-[Array&String]构建乘积数组

柔情只为你懂 2023-06-18 03:57 8阅读 0赞

### [点击查看剑指Offer全解【Java & Golang】实现][Offer_Java _ Golang] ###

### 题目描述 ###

给定一个数组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\[i\]的值等于数组A中除了A\[i\]之外所有值的乘积。

第一种思路是暴力解法，即每次计算B\[i\]时，都遍历一遍A并且求每个元素的乘积(排除A\[i\])，这种做法的时间复杂度接近于O(n^2)。

第二种思路是先累积A各个元素的值得到temp，若A\[i\]不为0时，则B\[i\] = temp / A\[i\];若A\[i\]为0，则使用思路一的做法，顺序遍历再次累积获取最后结果。这种做法不必要全部都遍历一遍。

第三种思路可以通过画图得知：可以使用B和A组成一个正方形，并且将B\[i\]都设置为1，然后1连线之下的称为下三角区域，之上的称为上三角区域。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70]

### Java第二种思路实现 ###

import java.util.ArrayList;
    import java.util.HashMap;
    public class Solution { 
        public int[] multiply(int[] A) { 
            if (A.length == 0) { 
                return A;
            }
            int temp = 1;
            for (int i = 0; i < A.length; i++) { 
                temp *= A[i];
            }
            int[] B = new int[A.length];
            for (int i = 0; i < B.length; i++) { 
                if (A[i] != 0) { 
                    B[i] = temp / A[i];
                } else { 
                    // 顺序累积
                    int temp2 = 1;
                    for (int j = 0; j < B.length; j++) { 
                        if (j != i) { 
                            temp2 *= A[j];
                        }
                    }
                    B[i] = temp2;
                }
            }
            return B;
        }
    }

### Java第三种思路实现 ###

链接：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46?f=discussion
    来源：牛客网
    
    public class Solution { 
        public int[] multiply(int[] A) { 
            int length = A.length;
            int[] B = new int[length];
            if(length != 0 ){ 
                B[0] = 1;
                //计算下三角连乘
                for(int i = 1; i < length; i++){ 
                    B[i] = B[i-1] * A[i-1];
                }
                int temp = 1;
                //计算上三角
                for(int j = length-2; j >= 0; j--){ 
                    temp *= A[j+1];
                    B[j] *= temp;
                }
            }
            return B;
        }
    }

[Offer_Java _ Golang]: https://blog.csdn.net/pbrlovejava/article/category/9502189
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630204515585.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BicmxvdmVqYXZh,size_16,color_FFFFFF,t_70