題目

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

示例:

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

提示：題目數(shù)據(jù)保證數(shù)組之中任意元素的全部前綴元素和后綴（甚至是整個(gè)數(shù)組）的乘積都在 32 位整數(shù)范圍內(nèi)。

說明: ?請不要使用除法，且在 O(n) 時(shí)間復(fù)雜度內(nèi)完成此題。

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

解法

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

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

對此由以下解法：

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

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

我們需要用兩個(gè)循環(huán)來填充 L 和 R 數(shù)組的值。對于數(shù)組 L，L[0] 應(yīng)該是 1，因?yàn)榈谝粋€(gè)元素的左邊沒有元素。對于其他元素：L[i] = L[i-1] * nums[i-1]。

同理，對于數(shù)組 R，R[length-1] 應(yīng)為 1。length 指的是輸入數(shù)組的大小。其他元素：R[i] = R[i+1] * nums[i+1]。

當(dāng) R 和 L 數(shù)組填充完成，我們只需要在輸入數(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;
 }
}

復(fù)雜度分析

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

空間復(fù)雜度：O(N)，其中 N 指的是數(shù)組 nums 的大小。使用了 L 和 R 數(shù)組去構(gòu)造答案，L 和 R 數(shù)組的長度為數(shù)組 nums 的大小。

算法二：共享數(shù)組方式

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

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

1. 在兩指針交會(huì)前，只需對數(shù)組進(jìn)行簡單的填充即可;

2. 在兩者交互時(shí)（僅發(fā)生在奇數(shù)長度）其填充值為 left*right。

3. 兩者交匯后，數(shù)組的值應(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;
    }
}

復(fù)雜度分析

時(shí)間復(fù)雜度： O(N)，同上一解題方式相同，進(jìn)行了一次長度為N的循環(huán)，其時(shí)間復(fù)雜度為O(N)。

空間復(fù)雜度：O(1)，題目中所述，返回?cái)?shù)組的空間不算，故所使用的額外存儲(chǔ)空間為 left 和 right。故只有常數(shù)級(jí)別的空間復(fù)雜度。

Atas ialah kandungan terperinci [LeetCode]238. 除自身以外數(shù)組的乘積解題思路. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!