[python 刷题] 238 Product of Array Except Self

[python 刷题] 238 Product of Array Except Self

题目：

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.

这里题目中 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer 就很明显提示说用 prefix sum 了

另外还有就是题目要求的 $O(n)$ 的时间复杂度，以及不能用除法

题目要求是获取除了自己以外的所有乘积，以题目中的案例 [1,2,3,4]，它的乘积可以理解成这样的计算方式:

其中 prefix 是所有的前置乘积，postfix 是所有的后置乘积

解法如下：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = [1] * (len(nums) + 2)
        postfix = [1] * (len(nums) + 2)

        for i in range(2, len(prefix)):
            prefix[i] = prefix[i - 1] * nums[i - 2]

        for i in range(len(prefix) - 3, 0, -1):
            postfix[i] = postfix[i + 1] * nums[i]

        res = [1] * len(nums)

        for i in range(0, len(nums)):
            print(prefix[i + 1])
            res[i] = prefix[i + 1] * postfix[i + 1]

        return res

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

但是在实际写的时候发现 map index 的处理稍微麻烦了一些，所以又找了一下其他的写法，发现了一个优化的写法：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        for i in range(1, len(nums)):
            res[i] = res[i-1] * nums[i-1]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res

1
2
3
4
5
6
7
8
9
10
11
12

这个写法将原本的 3 pass 缩减成了 2 pass，即只有两个循环，主要是因为没有保存 postfix 这个数组，而是一边迭代一边计算 postfix

同时，prefix 的值直接存在了返回值中，跳掉了表格中下标为 0 的占位符

虽然时间和空间的大 O 还是一样的，不过速度和性能上确实好了不少

---

同样的解法也可以用来解 2012. Sum of Beauty in the Array

题目：

You are given a 0-indexed integer array nums. For each index i (1 <= i <= nums.length - 2) the beauty of nums[i] equals:

• 2, if nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1.
• 1, if nums[i - 1] < nums[i] < nums[i + 1], and the previous condition is not satisfied.
• 0, if none of the previous conditions holds.
  Return the sum of beauty of all nums[i] where 1 <= i <= nums.length - 2.

解法：

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * n
        res = 0

        for i in range(n):
            prefix[i] = max(prefix[i - 1] if i > 0 else nums[i], nums[i])

        suffix = nums[n - 1]
        for i in range(n - 2, 0, -1):
            if prefix[i - 1] < nums[i] < suffix:
                res += 2
            elif nums[i - 1] < nums[i] < nums[i + 1]:
                res += 1

            suffix = min(suffix, nums[i])

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