Product of Array Except Self

Posted on | Edited on | In | | Views:

238. Product of Array Except

Given an array nums of $n$ integers where $n>1$, return an array output such that output[i] is equal to the product of all the elemetns of nums except nums[i]

题目说的是, 给一个array, 要求返回另外一个数组. 要求是, 返回的数组里面的是原数组其他数的乘积.
比如说:
[1, 2, 3, 4]是输入, 那么输出是 [24, 12, 8, 6]. 因为 $24 = 2 \times 3 \times 4$, $12 = 1 \times 3 \times 4$.

思路

要解这道题, 可以运用两个指针. 从前往后扫, 得出 $0$ 到 $i-1$ 的乘积. 从后往前扫, 得出 $i+1$ 到 最后一位的乘积. 然后将两次扫到的结果相乘.

这里的输入还是 [1, 2, 3, 4].
首先, 从前往后扫. 得出 f = [1, 1, 2, 6]. 然后再从后往前扫, 得出 b =[24, 12, 4, 1]. 然后将两个数组相乘, 就是题目要求的结果.

仔细看两次的扫描结果, 很容易发现, 当$i=2$的时候, f[2] = nums[0] * nums[1], b[2] = nums[3] * 1. 他们相乘的结果刚好是 nums[0] * nums[1] * nums[3].

Code

1
2
3
4
5
6
7
8
9
10
11
def productExceptSelf(nums):
    a = len(nums) * [1]
    b = len(nums) * [1]
        
    for i in range(1, len(nums)):
        a[i] = nums[i-1] * a[i-1]
        
    for i in reversed(range(len(nums)-1)):
        b[i] = nums[i+1] * b[i+1]
        
    return [i*j for i,j in zip(a,b)]

EOF