[每日一道小算法（十八）][数组] 构建乘积数组（剑指offer习题）

约定不等于承诺〃 2023-07-04 11:23 13阅读 0赞

前言：  
这几天都在做剑指offer上面的习题，所以基本都是上面的习题，推荐你们也做一下，发散思维。 但凡做剑指的题，都会做上标注的。

### 题目描述 ###

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

### 题目解析 ###

其实这道题的思路很好想，我们先把这个进行分解如下：  
C\[i\] = A\[0\]`*`A\[1\]`*`…`*`A\[i-1\] = C\[i-1\]`*`A\[i-1\]。  
D\[i\]=A\[i+1\]`*`…`*`A\[n-1\] = A\[i+1\] `*` D\[i+1\]；  
根据这个我们可以先分别求出来C\[i\]和D\[i\]，在最后求解最后的B\[i\]。

### 代码样例 ###

public class Solution{ 
    	public int[] multiply(int[] A)
    	{ 
    		if(A.length<=0 || A == null)
    		{ 
    			return null;
    		}
    		int[] C = new int[A.length];
    		C[0] = 1;
    		for(int i=0;i<C.length;i++)
    		{ 
    			C[i] = C[i-1]*A[i-1];
    		}
    		int[] D = new int[A.length];
    		D[D.length-1] = 1;
    		for(int i=D.length-2;i>=0;i++)
    		{ 
    			D[i] = D[i+1] * A[i+1];
    		}
    		int[] result = new int[A.length];
    		for(int i=0;i<result.length;i++)
    		{ 
    			result[i] = C[i] * D[i];
    		}
    		return result;
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指Offer五十一：构建乘积数组

题干 \\给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\]A\[1\]…A\[i-1\]A\

朴灿烈づ我的快乐病毒、/ 2023年07月24日 05:42/ 0 赞/ 11 阅读

相关剑指Offer:构建乘积数组

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

男娘i/ 2023年07月17日 02:41/ 0 赞/ 27 阅读

相关 [每日一道小算法（十八）][数组] 构建乘积数组（剑指offer习题）

前言：这几天都在做剑指offer上面的习题，所以基本都是上面的习题，推荐你们也做一下，发散思维。但凡做剑指的题，都会做上标注的。题目描述给定一个数组A\[0

约定不等于承诺〃/ 2023年07月04日 11:23/ 0 赞/ 14 阅读

相关构建乘积数组（剑指offer）

给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\A\[1\]\...\A\[i-1\]\

旧城等待，/ 2023年02月22日 13:37/ 0 赞/ 39 阅读

相关剑指offer—构建乘积数组

剑指offer题目描述：给定一个数组`A[0,1,...,n-1]`,请构建一个数组`B[0,1,...,n-1],`其中B中的元素`B[i]=A[0]A[1]...

拼搏现实的明天。/ 2022年11月13日 01:55/ 0 赞/ 196 阅读

相关剑指offer_构建乘积数组

/ 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]

怼烎@/ 2022年06月09日 10:09/ 0 赞/ 207 阅读

相关剑指offer-构建乘积数组

> 描述题目：给定一个数组A \[0,1，…，N-1\]，请构建一个数组B \[0,1，…，N-1\]，其中乙中的元素B \[I \] = A \[0\] \ A \[1\]

曾经终败给现在/ 2022年05月26日 06:40/ 0 赞/ 230 阅读

相关剑指Offer-构建乘积数组

题目描述给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\]×A\[1\]×…×A\[i-1\

朱雀/ 2022年04月24日 10:34/ 0 赞/ 247 阅读

相关剑指Offer——构建乘积数组

题目描述：给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\A\[1\]\...\A\

约定不等于承诺〃/ 2021年09月30日 02:08/ 0 赞/ 348 阅读

相关剑指offer：构建乘积数组

试题：给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\]A\[1\]…\A\[i-1\]A\[

骑猪看日落/ 2021年06月11日 15:14/ 0 赞/ 416 阅读