题目描述
给定一个整数数组 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;
}时间复杂度分析：
- 第一个循环遍历数组，时间复杂度为 O(n)。
- 第二个循环遍历数组，时间复杂度为 O(n)。
- 总体时间复杂度为 O(n)。
空间复杂度分析：
- 只使用了一个辅助数组来存储左侧的乘积，空间复杂度为 O(n)。
结论
本文介绍了题目"除自身以外数组的乘积"的详细描述，并给出了三种解法：暴力法、左右乘积列表和空间优化。下面是它们的时间和空间复杂度的总结：
解法 | 时间复杂度 | 空间复杂度 |
暴力法 | O(n^2) | O(n) |
左右乘积列表 | O(n) | O(n) |
空间优化 | O(n) | O(n) |
从复杂度分析可以看出，解法二和解法三都能够在线性时间内完成计算，而且空间复杂度也相对较低。因此，解法二和解法三是更优的解决方案。
在实际应用中，根据具体的问题和要求，选择合适的解法可以提高算法的效率和性能。希望本文能够帮助读者理解和掌握解决"除自身以外数组的乘积"问题的不同解法，并在实际编程中得到应用。如果想要了解更多数组相关的问题和解法，建议进一步学习相关的算法和数据结构知识。
