我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面試題66. 構建乘積數組

題目

給定一個數組 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]。不能使用除法。

示例:

輸入: [1,2,3,4,5]
輸出: [120,60,40,30,24]

提示：

• 所有元素乘積之和不會溢出 32 位整數
• a.length ⇐ 100000

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-錯位從前往後和從後往前連乘兩遍

思路解析：

• 第一遍從i位置開始連乘，但是每次的乘積都給到新數組的i+1位置，遍歷完時最後的len-1位置已經得到最終結果，len-1前面的逐個缺少1，2，3，4...個其他位置的乘因數，但是已經避免了乘自己i位置的值；
• 第二遍從i=len-1位置開始連乘，這次每次的乘積和新數組i-1位置的相乘作為新數組i-1位置的最後結果；

更清晰的理解：

• 第一遍從前往後其實是計算了[0,i）的連乘作為i位置的結果；
• 第二遍從後往前是計算(i,len-1]的連乘結果，那麼再與第一遍得到的i位置的結果相乘就是[0,len-1]不包含i位置的連乘結果了；

思路還是很清晰的哈~

演算法複雜度:

• 時間複雜度： \({\color{Magenta}{\Omicron\left(n\right)}}\)
• 空間複雜度： \({\color{Magenta}{\Omicron\left(1\right)}}\) 不包含結果數組所需空間

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年5月14日 下午10:23:21 
 * @Description: 面試題66. 構建乘積數組
 *
 */
public class LeetCode_Offer_66 {

}

class Solution_Offer_66 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月14日 下午10:23:49 
	 * @param: @param a
	 * @param: @return
	 * @return: int[]
	 * @Description: 1-錯位連乘兩遍即可；
	 *
	 */
	public int[] constructArr(int[] a) {
		if (a.length < 2) {
			return a;
		}
		int len = a.length;
		int[] b = new int[len];
		int c = 1;
		for (int i = 0; i < len; i++) {
			b[i] = c;
			c *= a[i];
		}
		c = 1;
		for (int i = len - 1; i >= 0; i--) {
			b[i] *= c;
			c *= a[i];
		}
		return b;
	}
}