10-24 LeetCode 238. Product of Array Except Self

Product of Array Except Self

Description

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.)

提供一个包含n个数的数组nums，返回一个数组output, 其中output[i]等于nums中除了第i个数以外其他所有数的乘积。

在O(n)时间复杂度内解决这个问题，并且不使用除法。

Example：

提供：

[1, 2, 3, 4]

返回：

[24, 12, 8, 6]

挑战：

用常数的额外空间完成这题，output不算额外空间。

Solution 1:

这题我没有做出来。参考了别人的答案后，发现是我数学不过关 = =！

首先我们假设nums数组为

[a1, a2, a3, a4]，

则可以得出output数组为

[a2a3a4, a1a3a4, a1a2a4, a1a2a3**]

然后发现这个数组可以由下面这两个数组的对应项相乘得到：

[1, a1, a1*a2, a1*a2*a3]
[a2*a3*a4, a3*a4, a4, 1]

于是我们就构造这样的两个数组

代码：

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        array1, array2 = [], []
        array1.append(1)
        for i in range(1, len(nums)):
            array1.append(array1[i-1] * nums[i-1])
        
        array2.append(1)
        nums = nums[::-1]
        for i in range(1, len(nums)):
            array2.append(array2[i-1] * nums[i-1])
        
        array2 = array2[::-1]

        for i in range(len(array2)):
            array1[i] *= array2[i]
    
        return array1

Solution2:

上面的方法虽然满足了时间复杂度为O(n),但是空间复杂度由于多用了array2而不是常数。所以这个方法对上面方法的一个优化。这个方法用一个变量num记录原本的array2数组，使额外空间变成常量1.

代码：

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        array1, num = [], 1
        array1.append(1)
        for i in range(1, len(nums)):
            array1.append(array1[i-1] * nums[i-1])
        
        for i in list(range(0, len(nums)-1))[::-1]:
            num *= nums[i+1]
            array1[i] *= num
        return array1

感想

做这件事有点耗时啊！