剑指Offer:构建乘积数组

男娘i 2023-07-17 02:41 13阅读 0赞

对于拿到这道题的我，只想到了暴力求解：  
当看到大佬们的思路时，我只想说兄弟们咱们题做的还是太少，奋键盘刷题（奋笔图书）吧；  
方法一：**暴力求解**

import java.util.*;
    public class Solution { 
        public int[] multiply(int[] A) { 
            int[] B = new int[A.length];
            Arrays.fill(B,1);
            for(int i = 0;i < B.length;i++){ 
                for(int j = 0;j < A.length;j++){ 
                    if(j == i){ 
                        continue;
                    }
                    B[i] *= A[j];
                }
            }
             
            return B;
        }
    }

方法二：剑指的思路  
**B\[i\]的值可以看作下图的矩阵中每行的乘积。**  
**下三角**用连乘可以很容求得，**上三角**，从下向上也是连乘。  
因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B\[i\]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JhY2twYWNlXw_size_16_color_FFFFFF_t_70]

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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JhY2twYWNlXw_size_16_color_FFFFFF_t_70]: /images/20230528/ce279c9d7f064659b91a5de33ba74286.png