【題目】

　　給定一個整型數組arr，返回不包含本位置值的累乘數組。?
　　例如，arr = [2, 3, 4, 1]，返回[12, 8, 24, 6]，即除自己以外，其他位置上的累乘。

【要求】

時間復雜度O(N)
除需要返回的結果數組外，額外空間復雜度O(1)。
【基本思路】

　　方法一。使用除法進行實現。所有數的累積記為all，如果數組中不存在0，那么結果數組中每一個位置的值為 all/arr[i]；如果數組中存在一個0，那么除該位置的值為all，其余都是0；如果有兩個或者兩個以上的0，結果數組全為0
?

def product(arr):if arr == None or len(arr) == 0:return []all_ = 1res = [0 for i in range(len(arr))]count = 0for i in range(len(arr)):if arr[i]!=0:all_ *= arr[i]else:count +=1if count==0:res = [all_/item for item in arr]if count==1:for i in range(len(arr)):if arr[i] == 0:res[i] = all_return res

方法二。不使用除法進行實現。分別使用輔助兩個數組left和right，其中left表示數組從左到右的累乘結果（即left[i] = arr[0…i]的累乘）；相反，right表示數組從右到左的累乘結果。那么對于結果數組res，res[i] = left[i-1] * right[i+1]。?
　　實際上，并不需要額外聲明兩個輔助數組。可以復用結果數組res，即先將res當輔助數組用，再把res調整為結果數組即可。具體實現見如下代碼:

def product2(arr):if arr == None or len(arr) < 2:return []res = [0 for i in range(len(arr))]res[0] = arr[0]for i in range(1,len(arr)):res[i] = res[i-1] * arr[i]tmp = 1for i in range(len(arr)-1):res[i] = res[i-1]*tmptmp *= arr[i]res[0] =tmpreturn res

?

總結

以上是生活随笔為你收集整理的不包含本位置值的累乘数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。