題目

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

範(fàn)例:

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

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

說(shuō)明: ?請(qǐng)不要使用除法，且在 O(n) 時(shí)間複雜度內(nèi)完成此題。

進(jìn)階： 你可以在常數(shù)空間複雜度內(nèi)完成這個(gè)題目嗎？ （ 出於對(duì)空間複雜度分析的目的，輸出數(shù)組不被視為額外空間。）。

解法

拿到題目首先的想法是：兩次for循環(huán)，一次積一次做除法。但後來(lái)發(fā)現(xiàn)說(shuō)明中註明不要使用除法，便只能向其他方法。

既然是算除了自己之外的累乘，便可以以當(dāng)前所在位置為分割點(diǎn)，分別計(jì)算左側(cè)元素乘積 和 右側(cè)元素乘積，之後再進(jìn)行相乘。

對(duì)此由以下解法：

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

初始化兩個(gè)空數(shù)組L 和R。對(duì)於給定索引 i，L[i] 代表的是 i 左側(cè)所有數(shù)字的乘積，R[i] 代表的是 i 右側(cè)所有數(shù)字的乘積。

我們需要用兩個(gè)迴圈來(lái)填入 L 和 R 陣列的值。對(duì)於陣列 L，L[0] 應(yīng)該是 1，因?yàn)榈谝粋€(gè)元素的左邊沒(méi)有元素。對(duì)於其他元素：L[i] = L[i-1] * nums[i-1]。

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

當(dāng)R 和L 陣列填入完成，我們只需要在輸入數(shù)組上迭代，且索引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;
 }
}

複雜度分析

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

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

演算法二：共享陣列方式

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

定義傳回?cái)?shù)組returnNums 並將其看作共享數(shù)組，同時(shí)從左右兩端填充資料；之後定義left,right 來(lái)儲(chǔ)存左右乘積並循環(huán)迭代更新。

1. 在兩個(gè)指標(biāo)交會(huì)前，只需對(duì)陣列進(jìn)行簡(jiǎn)單的填滿即可;

2. 在兩者互動(dòng)時(shí)（僅發(fā)生在奇數(shù)長(zhǎng)度）其填滿值為left*right。

3. 兩者交會(huì)後，陣列的值應(yīng)填入最終值：因?yàn)樽髠?cè)部分已經(jīng)儲(chǔ)存了左乘積，而即將計(jì)算得到右乘積；右側(cè)部分已儲(chǔ)存了右乘積，即將獲得左乘積。故直接相乘即可。 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;    // 臨時(shí)存儲(chǔ)
        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){  // 兩指針為交會(huì)
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 兩指針重合，奇數(shù)位情況下發(fā)生
                returnNums[i] = left*right;
            }else{              // 兩指針錯(cuò)位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

複雜度分析

#時(shí)間複雜度: O(N )，同上一解題方式相同，進(jìn)行了長(zhǎng)度為N的循環(huán)，其時(shí)間複雜度為O(N)。

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

以上是[LeetCode]238. 除自身以外數(shù)組的乘積解題思路的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！