4 min read leetcode

238. Product of Array Except Self

238. Product of Array Except Self
Photo by Markus Spiske / Unsplash

題目理解

題目：238. Product of Array Except Self

給定一個整數陣列 nums，請你返回一個陣列 answer，其中 answer[i] 等於陣列 nums 中除 nums[i] 本身之外，其餘所有元素的乘積。請在 O(n) 的時間複雜度內完成此任務，且不能使用除法運算。

限制條件

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • 保證答案符合 32 位元整數範圍。

解題思路

解法一：暴力法

最直接的想法是對於每個元素 nums[i]，計算陣列中除了 nums[i] 之外的所有元素的乘積。然而這需要兩層迴圈：

  • 時間複雜度：O(n²)，因為對於每個元素，都需要遍歷整個陣列。
  • 缺點：無法滿足題目要求的 O(n) 時間複雜度。

解法二：前綴積與後綴積

為了達到 O(n) 的時間複雜度，我們可以使用前綴積和後綴積的概念：

  1. 前綴積（prefix product）：位置 i 的前綴積是從陣列開始到位置 i - 1 的所有元素的乘積。
  2. 後綴積（suffix product）：位置 i 的後綴積是從位置 i + 1 到陣列結尾的所有元素的乘積。

步驟：

  1. 初始化：
    • 建立兩個大小為 n 的陣列 left 和 right，用來存放每個位置的前綴積和後綴積。
    • 設定 left[0] = 1，因為在位置 0 前沒有元素。
    • 設定 right[n - 1] = 1，因為在位置 n - 1 後沒有元素。
  2. 計算前綴積：
    • 從左到右遍歷陣列：
      • left[i] = left[i - 1] * nums[i - 1]
  3. 計算後綴積：
    • 從右到左遍歷陣列：
      • right[i] = right[i + 1] * nums[i + 1]
  4. 計算結果：
    • 對於每個位置 i：
      • answer[i] = left[i] * right[i]
  • 時間複雜度：O(n)
  • 空間複雜度：O(n)，因為使用了額外的陣列 left 和 right。

解法三：優化的前綴積

為了降低空間複雜度到 O(1)（不計輸出陣列 answer），我們可以在一個陣列中完成所有計算：

步驟：

  1. 初始化：
    • 建立大小為 n 的結果陣列 answer，並將 answer[0] 設為 1。
  2. 計算前綴積：
    • 從左到右遍歷陣列，計算每個位置的前綴積：
      • answer[i] = answer[i - 1] * nums[i - 1]
  3. 計算後綴積並更新結果：
    • 初始化一個變數 suffix，初始值為 1，代表後綴積。
    • 從右到左遍歷陣列，對每個位置：
      • answer[i] = answer[i] * suffix
      • suffix = suffix * nums[i]

這樣，我們在一次遍歷中同時完成了前綴積和後綴積的計算，並更新了結果。

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)，除了輸出陣列 answer 外，未使用其他額外的陣列。

程式碼

C++ 實作

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n, 1);
        for (int i = 1; i < n; i += 1) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
};

Java 實作

class Solution {
    public int[] productExceptSelf(int[] nums) {
        final int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;

        for (int i = 1; i < n; i += 1) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i -= 1) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
}

時間與空間複雜度分析

  • 時間複雜度：O(n)
    • 分析：我們對陣列進行了兩次遍歷：
      • 第一次遍歷：計算每個位置的前綴積，時間為 O(n)。
      • 第二次遍歷：計算後綴積並更新結果，時間為 O(n)。
    • 總時間複雜度為 O(2n)，簡化為 O(n)。
  • 空間複雜度：O(1)（不計輸出陣列 answer）
    • 分析：除了輸出陣列 answer 外，我們只使用了常數級別的額外空間（例如變數 suffix）。因此，額外的空間複雜度為 O(1)。

Justin