Product of Array Except Self

Given an array of n integers where n> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[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.)

题目大意：

给定长度为n的整数数组nums，其中n > 1，返回输出数组output，满足output[i]等于除nums[i]之外其余各数的乘积。

不使用除法，在O(n)时间复杂度内完成此题目。

例如，给定 [1,2,3,4]，返回 [24,12,8,6]。

进一步思考：

你可以在常数空间复杂度内完成题目吗？（注意：输出数组不算在空间复杂度分析中）

解题思路：

首先想到的思路是计算全部数字的乘积，然后分别除以num数组中的每一个数（需要排除数字0）。然而，题目要求不能使用除法。

下面的解法非常巧妙，参考LeetCode Dicuss

链接地址：https://leetcode.com/discuss/46104/simple-java-solution-in-o-n-without-extra-space

由于output[i] = (x0* x1* ... * xi-1) * (xi+1* .... * xn-1)

因此执行两趟循环：

第一趟正向遍历数组，计算x0~ xi-1的乘积

第二趟反向遍历数组，计算xi+1~ xn-1的乘积

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        result = [1]*length
        left = 1
        right = 1
        # 循环nums中所有number，除了最后一个number， 因为我们求数字的左边乘机，永远都不需要乘以最后一个数，例如最后一个数字4的左边乘机是1*2*3
        for i in xrange(length-1):
            left *= nums[i]
            # nums中第一个数字（i＝0）的左边乘积就是1，所以我们从result中第二个数字（i＝1）开始储存
            result[i+1] = left
        for j in xrange(length-1, 0, -1):
            right *= nums[j]
            result[j-1] *=right
        return result