在處理數組相關的問題時，有時候需要計算除數組中某個元素以外的所有元素的乘積。這個問題可以通過多種方法解決。本文將首先給出題目的詳細描述，然后介紹三種解法，并提供相應的Java代碼示例。最后，對每種解法進行時間和空間復雜度的分析，幫助讀者評估解法的效率和性能。Thf28資訊網——每日最新資訊28at.com

Thf28資訊網——每日最新資訊28at.com

題目描述

給定一個整數數組 nums，返回一個數組 output，其中 output[i] 等于除 nums[i] 之外的所有元素的乘積。Thf28資訊網——每日最新資訊28at.com

注意：請不要使用除法，且在 O(n) 時間復雜度內完成此問題的解決。Thf28資訊網——每日最新資訊28at.com

示例：Thf28資訊網——每日最新資訊28at.com

輸入: [1, 2, 3, 4]Thf28資訊網——每日最新資訊28at.com

輸出: [24, 12, 8, 6]Thf28資訊網——每日最新資訊28at.com

解釋: 除了自身以外的乘積為：[2x3x4, 1x3x4, 1x2x4, 1x2x3] = [24, 12, 8, 6]Thf28資訊網——每日最新資訊28at.com

1. 解法一：暴力法

暴力法是最簡單直接的解法，即對于數組中的每個元素，都計算除自身以外的其他元素的乘積。具體步驟如下：Thf28資訊網——每日最新資訊28at.com

public int[] productExceptSelf(int[] nums) {   int n = nums.length;   int[] output = new int[n];      for (int i = 0; i < n; i++) {       int product = 1;       for (int j = 0; j < n; j++) {           if (i != j) {               product *= nums[j];          }      }       output[i] = product;  }      return output;}

時間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 外層循環遍歷數組，時間復雜度為 O(n)。
• 內層循環遍歷數組，時間復雜度為 O(n)。
• 總體時間復雜度為 O(n^2)。

空間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 使用了額外的數組 output 來存儲結果，空間復雜度為 O(n)。

2. 解法二：左右乘積列表

解法二利用兩個輔助數組，分別記錄每個元素左側和右側的乘積。具體步驟如下：Thf28資訊網——每日最新資訊28at.com

public int[] productExceptSelf(int[] nums) {   int n = nums.length;   int[] output = new int[n];      int[] leftProducts = new int[n];   int[] rightProducts = new int[n];      leftProducts[0] = 1;   for (int i = 1; i < n; i++) {       leftProducts[i] = leftProducts[i - 1] * nums[i - 1];  }      rightProducts[n - 1] = 1;   for (int i = n - 2; i >= 0; i--) {       rightProducts[i] = rightProducts[i + 1] * nums[i + 1];  }      for (int i = 0; i < n; i++) {       output[i] = leftProducts[i] * rightProducts[i];  }      return output;}

時間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 第一個循環遍歷數組，時間復雜度為 O(n)。
• 第二個循環遍歷數組，時間復雜度為 O(n)。
• 第三個循環遍歷數組，時間復雜度為 O(n)。
• 總體時間復雜度為 O(n)。

空間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 使用了兩個輔助數組來存儲左側和右側的乘積，空間復雜度為 O(n)。

3. 解法三：空間優化

解法三對解法二進行了空間優化，只使用一個輔助數組來記錄左側的乘積，并在計算右側乘積時即時更新結果。具體步驟如下：Thf28資訊網——每日最新資訊28at.com

public int[] productExceptSelf(int[] nums) {   int n = nums.length;   int[] output = new int[n];      output[0] = 1;   for (int i = 1; i < n; i++) {       output[i] = output[i - 1] * nums[i - 1];  }      int rightProduct = 1;   for (int i = n - 1; i >= 0; i--) {       output[i] *= rightProduct;       rightProduct *= nums[i];  }      return output;}

時間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 第一個循環遍歷數組，時間復雜度為 O(n)。
• 第二個循環遍歷數組，時間復雜度為 O(n)。
• 總體時間復雜度為 O(n)。

空間復雜度分析：Thf28資訊網——每日最新資訊28at.com

• 只使用了一個輔助數組來存儲左側的乘積，空間復雜度為 O(n)。

結論

本文介紹了題目"除自身以外數組的乘積"的詳細描述，并給出了三種解法：暴力法、左右乘積列表和空間優化。下面是它們的時間和空間復雜度的總結：Thf28資訊網——每日最新資訊28at.com

從復雜度分析可以看出，解法二和解法三都能夠在線性時間內完成計算，而且空間復雜度也相對較低。因此，解法二和解法三是更優的解決方案。Thf28資訊網——每日最新資訊28at.com

在實際應用中，根據具體的問題和要求，選擇合適的解法可以提高算法的效率和性能。希望本文能夠幫助讀者理解和掌握解決"除自身以外數組的乘積"問題的不同解法，并在實際編程中得到應用。如果想要了解更多數組相關的問題和解法，建議進一步學習相關的算法和數據結構知識。Thf28資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-54008-0.html除自身以外數組的乘積：三種解法及Java代碼示例

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 10分鐘了解Python黑魔法 Yield、Iterator、Generator

下一篇： jstat，一把Java程序員必備的瑞士軍刀