我的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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/195315.html
標籤：Java