Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Solution:
题目中说不要用到 division 并且要在线性时间内得出结果。
首先受上一题影响想想能不能位运算，但这题乘法是不大行的。
那么要如果扫描一遍就得出要求的Array呢？
想想我们遍历 Array 时我们可以干些什么，我们可以对当前秩所在位置进行操作，关键是我们还可以对当前秩前后常数位置也可以进行操作。
考虑当前遍历到的秩 i，我们可以把得出 ans[i] 的过程分为两部分：一部分是对于所有小于 i 的秩的元素的相乘，另一部分则是所有大于 i 的秩的元素的相乘。
独立地来完成这两部分并不难，只要在遍历一遍时，用一个变量记录已经遍历到的元素的乘积（不包括当前元素），乘到 ans[i]即可。
而这两个独立的部分其实也可以合成一个遍历来完成，因为只要知道了整个需要遍历的Array的长度，从左向右和从右向左只是一个取模的问题了。
代码如下：
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def productExceptSelf(self, nums):
n = len(nums)
ans = [1] * n
left_fac, right_fac = 1, 1
for i in range(n):
ans[i] *= left_fac
left_fac *= nums[i]
ans[n - i - 1] *= right_fac
right_fac *= nums[n - i - 1]
return ans