238. Product of Array Except Self

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

https://leetcode.com/problems/product-of-array-except-self/

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 10⁵
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Test Cases

1
2

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('nums, expected', [
    ([1,2,3,4], [24,12,8,6]),
    ([-1,1,0,-3,3], [0,0,9,0,0]),

    ([1,2,3,0,4,5,0,6], [0,0,0,0,0,0,0,0]),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.productExceptSelf(nums) == expected

    def test_solution2(self, nums, expected):
        sol = Solution2()
        assert sol.productExceptSelf(nums) == expected

Thoughts

answer[i] 可以由其左半边子数组之积，乘以右半边子数组之积得到，即 ans[i] = prod(nums[:i]) * prod(nums[i+1:])。

记 pl[i] = prod(nums[:i])，pr[i] = prod(nums[i+1:])，可以得到递推式：

$$pl[i]=\begin{cases} 1 & \text{if }i=0 \\ pl[i-1]\times nums[i-1] & \text{otherwise} \end{cases}$$

$$pr[i]=\begin{cases} 1 & \text{if }i=n-1 \\ pr[i+1]\times nums[i+1] & \text{otherwise} \end{cases}$$

按递推时初始化好 pl 和 pr 的所有值，然后遍历 i 计算所有的 answer。时间复杂度 O(n)，空间复杂度 O(n)。

Code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        pl = [1] * n
        pr = [1] * n
        for i in range(1, n):
            pl[i] = pl[i-1] * nums[i-1]
            j = n - 1 - i
            pr[j] = pr[j+1] * nums[j+1]

        return [pl[i] * pr[i] for i in range(n)]

Follow Up

如果限制 O(1) 空间，不能再禁用除法了吧（前边禁用除法感觉是为了强行动态规划）。

如果数组中没有零，则 ans[i] = prod(nums) // nums[i]。只需要 O(1) 空间存储这个数组之积。

如果数组中刚好有一个零，则对于所有 nums[i] != 0 的 i，都有 ans[i] = 0。而唯一的零对应的 answer 为所有非零数字之积。

如果数组中有超过一个零，则 answer 为全零数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        has_zero = False
        prod = 1
        for val in nums:
            if val == 0:
                if has_zero:
                    return [0] * n
                has_zero = True
            else:
                prod *= val

        if has_zero:
            return [not val and prod or 0 for val in nums]

        return [prod // val for val in nums]

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章