Eisen 筆記

#238. Product of Array Except Self

題目描述

給你一個整數陣列nums，回傳陣列answer，answer[i]等於除了nums[i]以外的乘積。

nums中的元素前綴與後綴數值數值的乘積保證會落在32位元整數區間。

你必須設計一個時間複雜度為O(n)的演算法並且不能使用除法運算子。

限制條件

  1. 2 <= nums.length <= 105
  2. -30 <= nums[i] <= 30
  3. nums中的元素前後數值數值的乘積保證會落在32位元整數區間。

解題思路

這題有點複雜，因此需要將問題拆分。 首先由於題目要求我們不能使用除法運算子，所以我們只能在處理的時候跳過當下的數值。 再來題目提到了兩個關鍵字，前綴與後綴，意思是從當下位置算起，當下位置前面的數字與當下位置後面的數字。 這其實就給了我們一個拆分問題的提示。 舉例來說：
nums = [1,2,3,4,5]
前綴與後綴就會如下
prefix = [constant, 1, 1*2, 1*2*3, 1*2*3*4 ]
suffix = [2*3*4*5 , 3*4*5, 4*5, 5 , constant]
可以發現到前綴*後綴，就會等於我們要的目標答案。

而分別設計前綴與後綴的演算法，會相較於直接設計題目的演算法容易。

先來看前綴演算法的設計：

var prefix = new int[nums.Length];
int constant = 1; 
int store = 1; 
for(int i=0;i<nums.Length;i++){
	prefix[i] = constant * store;
	store *= nums[i];
}

可以看到前綴的當前位置等於常數乘上儲存起來的前綴，之後將同樣位置的陣列元素儲存進前綴中。 舉例來說：

  • Start
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 0, 0, 0, 0]
    store = 1(constant)
  • Step 1
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 0, 0, 0, 0]
    store = 1(constant) * 1
  • Step 2
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 1, 0, 0, 0]
    store = 1(constant) * 1 * 2
  • Step 3
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 1, 1*2, 0, 0]
    store = 1(constant) * 1 * 2 * 3
  • Step 4
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 1, 1*2, 1*2*3, 0]
    store = 1(constant) * 1 * 2 * 3 * 4
  • Step 5
    nums = [1, 2, 3, 4, 5]
    prefix = [1, 1, 1*2, 1*2*3, 1*2*3*4]
    store = 1(constant) * 1 * 2 * 3 * 4 * 5

而後綴也是一樣的演算法結構，如下：

var suffix = new int[nums.Length];
int constant = 1;
int store = 1;
for(int i=suffix.Length-1;i>=0;i--){
	suffix[i] *= store;
	store *= nums[i];
}

計算完的結果如下：\

  • Suffix
    nums = [1, 2, 3, 4, 5]
    prefix = [2*3*4*5 ,3*4*5 ,4*5 ,5 ,1]
    store = 1(constant) * 5 * 4 * 3 * 2 * 1

接著只要將前綴後綴相乘，就會得到答案

Prefix & Suffix

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        //
        var prefix = new int[nums.Length];
        int constant = 1;
        int store = 1;
        for(int i=0;i<nums.Length;i++){
            prefix[i] = constant * store;
            store *= nums[i];
        }
        //
        var suffix = new int[nums.Length];        
        store = 1; 
        for(int i=suffix.Length-1;i>=0;i--){
            suffix[i] = constant * store;
            store *= nums[i];
        }
        // Sum
        var ans = new int[nums.Length];
        for(int i=0;i<nums.Length;i++){
            ans[i] = prefix[i] * suffix[i];
        }
        return ans;
    }
}

複雜度分析：

  • 時間複雜度：做了前綴、後綴、總乘積三個等於陣列長度的for迴圈，總共花了3n的時間，所以時間複雜度是O(n)。
  • 空間複雜度：空間使用上由於使用了前綴、後綴的空間，總乘積就是答案的空間，因此不算在內，但是仍然使用了2n的空間，因此空間複雜度為O(n)。

Follow-up

你可以將空間複雜度維持在O(1)嗎？(輸出的陣列不算在空間複雜度內)。

Optimization

前綴空間與後綴空間其實可以省略掉，只要將答案作為儲存空間就可以將空間複雜度減少至O(1)。

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {        
        var ans = new int[nums.Length];
        for(int i=0;i<ans.Length;i++) ans[i]=1;
        //prefix
        int store = 1;
        for(int i=0;i<nums.Length;i++){
            ans[i] *= store;
            store *= nums[i];
        }
        //suffix
        store = 1;
        for(int i=nums.Length-1;i>=0;i--){
            ans[i] *= store;
            store *= nums[i];
        }
        return ans;
    }
}

複雜度分析：

  • 時間複雜度：做了答案空間初始化、前綴、後綴三個等於陣列長度的for迴圈，總共花了3n的時間，所以時間複雜度是O(n)。
  • 空間複雜度：空間使用上只增加了答案的空間，但不算在內空間複雜度中，因此空間複雜度為O(1)。

學習重點

  • Math
Last Updated:
Contributors: eisen