小豆花儿 發表於 2025-12-17 09:00:00

剑指offer-51、构建乘积数组

<h2 id="题描述">题⽬描述</h2>
<p>给定⼀个数组A ,请构建⼀个数组B ，其中B 中的元素<code>B=A*A*...*A*A*...*A</code> 。不能使⽤除法。（注意：规定<code>B =A * A * ... * A，B = A * A * ... * A</code> ）</p>
<p>对于A ⻓度为1 的情况，B⽆意义，故⽽⽆法构建，因此该情况不会存在。</p>
<p>输⼊：<br>
输出：</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力">暴力</h3>
<p>对每个B都计算A中除A外所有元素的乘积，双重循环，外层遍历B的每个位置，内层遍历A数组跳过当前元素</p>
<pre><code class="language-java">public class Solution {
    public int[] multiply(int[] A) {
      if (A == null || A.length &lt;= 1) {
            return new int; // 根据题目要求，长度&lt;=1时返回空数组
      }
      
      int n = A.length;
      int[] B = new int;
      
      // 遍历每个B
      for (int i = 0; i &lt; n; i++) {
            int product = 1; // 初始化乘积为1
            
            // 计算A中除A外所有元素的乘积
            for (int j = 0; j &lt; n; j++) {
                if (j != i) { // 跳过当前元素A
                  product *= A;
                }
            }
            
            B = product; // 将结果存入B
      }
      
      return B;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，需要嵌套循环遍历数组</li>
<li><strong>空间复杂度</strong>：O(1)，除结果数组外只使用常数空间</li>
</ul>
<h3 id="左右乘积数组法空间换时间">左右乘积数组法（空间换时间）</h3>
<p>使用左右两个辅助数组存储乘积信息</p>
<p>思路：left表示A到A的乘积，right表示A到A的乘积</p>
<pre><code class="language-java">public class Solution {
    public int[] multiply(int[] A) {
      if (A == null || A.length &lt;= 1) {
            return new int;
      }
      
      int n = A.length;
      int[] B = new int;
      int[] left = new int;// 存储左侧乘积
      int[] right = new int; // 存储右侧乘积
      
      // 初始化边界值
      left = 1;   // B没有左侧元素，乘积为1
      right = 1;// B没有右侧元素，乘积为1
      
      // 计算左侧乘积：left = A × A × ... × A
      for (int i = 1; i &lt; n; i++) {
            left = left * A;
      }
      
      // 计算右侧乘积：right = A × A × ... × A
      for (int i = n-2; i &gt;= 0; i--) {
            right = right * A;
      }
      
      // 合并左右乘积得到最终结果：B = left × right
      for (int i = 0; i &lt; n; i++) {
            B = left * right;
      }
      
      return B;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，三次单层循环</li>
<li><strong>空间复杂度</strong>：O(n)，需要两个辅助数组</li>
</ul>
<p><strong>矩阵视角理解</strong>： 如果把问题看作矩阵，B就是去掉对角线元素A后，该行所有元素的乘积。</p>
<pre><code class="language-text">A =

B = 2 × 3 × 4 × 5 = 120(去掉A)
B = 1 × 3 × 4 × 5 = 60   (去掉A)
B = 1 × 2 × 4 × 5 = 40   (去掉A)
</code></pre>
<p><strong>左右分解策略：</strong></p>
<ul>
<li><code>left</code>= A × A × ... × A （i左边的乘积）</li>
<li><code>right</code>= A × A × ... × A （i右边的乘积）</li>
<li><code>B = left × right</code>（左右乘积相乘正好去掉A）</li>
</ul>
<h3 id="空间优化推荐">空间优化（推荐）</h3>
<p>在方法二的基础上优化空间使用，在结果数组B上直接进行左右乘积计算。</p>
<p>先用B数组存储左侧乘积，再用变量动态计算右侧乘积</p>
<pre><code class="language-java">public class Solution {
    public int[] multiply(int[] A) {
      if (A == null || A.length &lt;= 1) {
            return new int;
      }
      
      int n = A.length;
      int[] B = new int;
      
      // 第一步：计算左侧乘积并直接存入B
      B = 1; // B没有左侧元素
      for (int i = 1; i &lt; n; i++) {
            // B = A × A × ... × A
            B = B * A;
      }
      
      // 第二步：从右向左遍历，用temp变量累积右侧乘积
      int temp = 1; // 用于累积右侧乘积
      for (int i = n-1; i &gt;= 0; i--) {
            // B当前存储的是左侧乘积，乘以右侧乘积得到最终结果
            B = B * temp;
            // 更新temp，为下一个位置（i-1）准备右侧乘积
            temp = temp * A;
      }
      
      return B;
    }
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，两次遍历数组</li>
<li><strong>空间复杂度</strong>：O(1)，除结果数组外只使用常数空间</li>
</ul>
<p><strong>算法步骤详解</strong></p>
<ol>
<li>第一步：左侧乘积计算</li>
</ol>
<pre><code>初始: B = 1
i=1: B = B × A = 1 × 1 = 1
i=2: B = B × A = 1 × 2 = 2
i=3: B = B × A = 2 × 3 = 6
i=4: B = B × A = 6 × 4 = 24
此时B = (存储的是各位置的左侧乘积)
</code></pre>
<ol start="2">
<li>第二步：右侧乘积整合</li>
</ol>
<pre><code>初始: temp = 1
i=4: B = 24 × 1 = 24, temp = 1 × 5 = 5
i=3: B = 6 × 5 = 30, temp = 5 × 4 = 20
i=2: B = 2 × 20 = 40, temp = 20 × 3 = 60
i=1: B = 1 × 60 = 60, temp = 60 × 2 = 120
i=0: B = 1 × 120 = 120, temp = 120 × 1 = 120
最终B =
</code></pre>


</div>
<div id="MySignature" role="contentinfo">
    <p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19346940
頁: [1]
查看完整版本: 剑指offer-51、构建乘积数组