不包含本位置值的累乘数组

【题目】

　　给定一个整型数组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

 

总结

以上是生活随笔为你收集整理的不包含本位置值的累乘数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。