題目

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.

Example 1

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

Example 2

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

Constraints:

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

Follow up:
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.)

解釋題目

題目會給一個 array 叫 nums，假設是 nums = [1, 2, 3, 4]，需要遍歷整個 array，遍歷到的數字輸出會是，除了自己以外的其他三個數字相乘。舉例來說，遍歷到 1 時，輸出會是 2 * 3 * 4；遍歷到 2 時，輸出會是 1 * 3 * 4。所以，最後輸出會是 [24, 12, 8, 6]。這題還有另外的限制是不能使用除法，且時間複雜度必須是 O(n)。

思路(1)

  1. 這題因為不能使用除法，所以可以它拆成兩個步驟，也就是前綴積以及後綴積。因為每遍歷到一個元素，就必須把該元素前面的元素相乘，再乘上該元素後面的所有元素。

  2. 也就是說，可以先把每個元素前面的所有元素相乘，得到一個前綴積的陣列。接著，再把每個元素後面的所有元素相乘，得到一個後綴積的陣列。

  3. 以 [1, 2, 3, 4] 為例，

    • 1 的前綴積會是 1 ，因為 1 前面沒有任何元素，所以直接用 1 表示。1 乘以任何數字不會有任何影響。
    • 2 的前綴積也是 1，因為 2 前面只有一個元素 1。
    • 3 的前綴積是 1 * 2，因為 3 前面有兩個元素 1 跟 2。
    • 4 的前綴積是 1 * 2 * 3，因為 4 前面有三個元素 1 跟 2 跟 3。
      所以，陣列 [1, 2, 3, 4] 的前綴積陣列會是[1, 1, 2, 6]

  4. 以此類推，後綴積的計算如下:

    • 1 的後綴積會是 2 * 3 * 4 ，因為 1 後面有三個元素， 2 跟 3 跟 4。
    • 2 的後綴積是 3 * 4，因為 2 後面兩個元素 3 跟 4。
    • 3 的後綴積是 4，因為 3 後面只有一個元素 4。
    • 4 的後綴積是 1，因為 4 後面沒有任何元素，所以直接用 1 表示。1 乘以任何數字不會有任何影響。
      所以，陣列 [1, 2, 3, 4] 的後綴積陣列會是[24, 12, 4, 1]

  5. 最後，前綴積、後綴積兩陣列相乘，就會是最後的輸出，也就是 [24, 12, 8, 6]。

  6. 程式的寫法，會先初始化兩個陣列，分別是前綴積陣列 ( prefix ) [1, 1, 1, 1]、後綴積陣列 ( postfix ) [1, 1, 1, 1]。前綴積陣列比較好想，會從第一個元素開始，因為第零個元素是 1。前綴積第二個元素會是，prefix[1] * nums [1]，因為前綴積就是把前面的元素都乘過一遍了，所以只要把「第一個元素的的前綴積」 ( 也就是 prefix[-1] ) 乘上「第一個元素」 (也就是 nums [i-1] )，就會是第二個元素的前綴積。

  7. 後綴積也是一樣的概念。只不過要從陣列的「倒數第二個元素」開始 往前遍歷，後綴積陣列要從後面填回來的意思，因為最後一個元素的後綴積是 1。計算後綴積要善用 python 的 range(start, stop, step)，所以 range 是 range(n-2, -1, -1)，其中 stop 不能寫 0 因為會不包含第一個元素，所以通常用 -1 表示要遍歷到起始點。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = []
        n = len(nums)
        prefix = [1] * n
        postfix = [1] * n

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

        # postfix
        # start/stop/step
        for i in range(n - 2, -1, -1):
            postfix[i] = postfix[i + 1] * nums[i + 1]

        # prefix * postfix
        for i in range(n):
            value = prefix[i] * postfix[i]
            result.append(value)
        # result = [a * b for a, b in zip(prefix, postfix)]

        return result

思路(2)

  1. 這個方法是要做 follow up 的思路，因為可以用 O(1) 的空間複雜度解題，前提是 output 陣列不列入額外空間的計算。

  2. output 陣列初始化為 [1, 1, 1, 1]，此陣列不列入額外空間計算，主要是透過 prefix 跟 postfix 的累乘，去乘上 result 得到結果。

  3. prefix 跟 postfix 的初始值是 1。先算 prefix 或先算 postfix 都可以，因為他們的初始值都是 1 ，所以在乘上 result 時並不會有影響，可以用前綴積 [1, 1, 2, 6]，跟後綴積 [24, 12, 4, 1] 相乘去思考。不管先算 presfix 還是 postfix，1 * 24 或 6 * 1 並不影響最後 result 結果。

程式碼 (2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n

        # prefix
        prefix = 1
        for i in range(1, n):
          prefix = prefix * nums[i-1]
          result[i] = prefix

        # postfix
        # start/stop/step
        postfix = 1
        for i in range(n - 2, -1, -1):
            postfix = postfix * nums[i + 1]
            result[i] = postfix * result[i]

        return result