[LeetCode]238. 除自身以外數組的乘積解題思路

題目

給你一個長度為n 的整數數組nums，其中n > 1，返回輸出數組output ，其中output[i] 等於nums 中除nums[i] 之外其餘各元素的乘積。

範例:

輸入: [1,2,3,4]
輸出: [24,12,8,6]

提示：題目資料保證陣列之中任意元素的全部前綴元素和後綴（甚至是整個陣列）的乘積都在32 位元整數範圍內。

說明:  請不要使用除法，且在 O(n) 時間複雜度內完成此題。

進階： 你可以在常數空間複雜度內完成這個題目嗎？ （ 出於對空間複雜度分析的目的，輸出數組不被視為額外空間。）。

解法

拿到題目首先的想法是：兩次for循環，一次積一次做除法。但後來發現說明中註明不要使用除法，便只能向其他方法。

既然是算除了自己之外的累乘，便可以以當前所在位置為分割點，分別計算左側元素乘積 和 右側元素乘積，之後再進行相乘。

對此由以下解法：

演算法一（摘自LeetCode官方解法）：

初始化兩個空數組L 和R。對於給定索引 i，L[i] 代表的是 i 左側所有數字的乘積，R[i] 代表的是 i 右側所有數字的乘積。

我們需要用兩個迴圈來填入 L 和 R 陣列的值。對於陣列 L，L[0] 應該是 1，因為第一個元素的左邊沒有元素。對於其他元素：L[i] = L[i-1] * nums[i-1]。

同理，對於陣列 R，#R[length-1] 應為 1。 length 指的是輸入陣列的大小。其他元素：R[i] = R[i 1] * nums[i 1]。

當R 和L 陣列填入完成，我們只需要在輸入數組上迭代，且索引i 處的值為：L[i] * R[i]。

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

複雜度分析

#時間複雜度：O(N)，其中N 指的是陣列nums 的大小。預處理 L 和 R 數組以及最後的遍歷計算都是 O(N) 的時間複雜度。

空間複雜度：O(N)，其中 N 指的是陣列 nums 的大小。使用了 L 和 R 陣列去建構答案，L 和 R 陣列的長度為陣列 nums 的大小。

演算法二：共享陣列方式

整體想法和官方解題思路相同：左乘*右乘。

定義傳回數組returnNums 並將其看作共享數組，同時從左右兩端填充資料；之後定義left,right 來儲存左右乘積並循環迭代更新。

1. 在兩個指標交會前，只需對陣列進行簡單的填滿即可;

2. 在兩者互動時（僅發生在奇數長度）其填滿值為left*right。

3. 兩者交會後，陣列的值應填入最終值：因為左側部分已經儲存了左乘積，而即將計算得到右乘積；右側部分已儲存了右乘積，即將獲得左乘積。故直接相乘即可。 returnNums[i] = left 且# returnNums[j] = right。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

複雜度分析

#時間複雜度: O(N )，同上一解題方式相同，進行了長度為N的循環，其時間複雜度為O(N)。

空間複雜度：O(1)，題目所述，傳回陣列的空間不算，故所使用的額外儲存空間為left 和right 。故只有常數等級的空間複雜度。

以上是[LeetCode]238. 除自身以外數組的乘積解題思路的詳細內容。更多資訊請關注PHP中文網其他相關文章！