除自身以外数组的乘积：三种解法及Java代码示例_Java教程

除自身以外数组的乘积：三种解法及Java代码示例

2023-12-25 15:38科学随想录 Java教程

在处理数组相关的问题时，有时候需要计算除数组中某个元素以外的所有元素的乘积。这个问题可以通过多种方法解决。本文将首先给出题目的详细描述，然后介绍三种解法，并提供相应的Java代码示例。最后，对每种解法进行时间

在处理数组相关的问题时，有时候需要计算除数组中某个元素以外的所有元素的乘积。这个问题可以通过多种方法解决。本文将首先给出题目的详细描述，然后介绍三种解法，并提供相应的Java代码示例。最后，对每种解法进行时间和空间复杂度的分析，帮助读者评估解法的效率和性能。

除自身以外数组的乘积：三种解法及Java代码示例

题目描述

给定一个整数数组 nums，返回一个数组 output，其中 output[i] 等于除 nums[i] 之外的所有元素的乘积。

注意：请不要使用除法，且在 O(n) 时间复杂度内完成此问题的解决。

示例：

输入: [1, 2, 3, 4]

输出: [24, 12, 8, 6]

解释: 除了自身以外的乘积为：[2x3x4, 1x3x4, 1x2x4, 1x2x3] = [24, 12, 8, 6]

1. 解法一：暴力法

暴力法是最简单直接的解法，即对于数组中的每个元素，都计算除自身以外的其他元素的乘积。具体步骤如下：

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;
}

时间复杂度分析：

外层循环遍历数组，时间复杂度为 O(n)。
内层循环遍历数组，时间复杂度为 O(n)。
总体时间复杂度为 O(n^2)。

空间复杂度分析：

使用了额外的数组 output 来存储结果，空间复杂度为 O(n)。

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

解法二利用两个辅助数组，分别记录每个元素左侧和右侧的乘积。具体步骤如下：

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;
}

时间复杂度分析：

第一个循环遍历数组，时间复杂度为 O(n)。
第二个循环遍历数组，时间复杂度为 O(n)。
第三个循环遍历数组，时间复杂度为 O(n)。
总体时间复杂度为 O(n)。

空间复杂度分析：

使用了两个辅助数组来存储左侧和右侧的乘积，空间复杂度为 O(n)。

3. 解法三：空间优化

解法三对解法二进行了空间优化，只使用一个辅助数组来记录左侧的乘积，并在计算右侧乘积时即时更新结果。具体步骤如下：

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;
}

时间复杂度分析：