给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解 :
- 这道题看起来非常容易，直接把数组中所有元素的乘积算出来
- 计算某个位置的值时，直接用总的乘积 / 当前元素的值即可得到最终结果
- 但是题目中有明确要求，不得使用除法
- 所以想线性时间复杂度的方法不太容易想
思路一 ： 暴力法
- 暴力法很容易想到
- 当计算第 i 位的值时，取出 除第 i 位以外的元素，计算乘积
- 此算法毫无疑问是正确的，但是时间复杂度很高，存在大量冗余的计算
- 提交后，超时了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
*
* 暴力法
* 暴力法很容易想到
* 当计算 i 位置的值时，取出 除i位置以外的元素，计算乘积
*
* 时间复杂度 : O(N ^ 2)
* 空间复杂度 : O(1)
*
* */
public int[] constructArr(int[] a) {
if (a == null || a.length == 0) return a;
int[] res = new int[a.length];
for (int i = 0; i < a.length; i++) {
int cur = 1;
for (int j = 0; j < a.length; j++) {
if (i == j) continue;
cur += a[j];
}
res[i] = cur;
}
return res;
}
|
复杂度分析 :
时间复杂度 : O(N ^ 2) 两遍暴力循环
空间复杂度 : O(1) 没有使用额外的存储空间
思路二: 线性时间复杂度的优化
-
在一个评论中看到，这道题可以看作 从前往后 和 从后往前的两遍 dp，深以为然
-
分别计算出某元素，前边所有元素的积 和 后边元素的积
-
两者的成绩，也就是要求的除自身以外的所有元素的乘积
-
我们使用 prev数组 存储 i 元素 前边所有元素的乘积
-
使用 next数组 存储 i 元素。后边所有元素的乘积
-
最终结果数组 res[i] = prev[i] * next[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/**
*
* 分别计算出某元素 前边所有元素的积 和 后边所有元素的积
* 两者的乘积，就是要求的除自身以外的子数组的乘积
*
* 我们使用 prev数组 存储 i 元素 前边所有元素的乘积
* next数组 存储 i 元素 后边所有元素的乘积
*
* 最终的结果数组 res[i] = prev[i] * next[i]
*
* 时间复杂度 : O(N)
* 空间复杂度 : O(N)
*
* */
public int[] constructArr1(int[] a) {
if (a == null || a.length == 0) return a;
int[] prev = new int[a.length];
prev[0] = 1;
for (int i = 1; i < a.length; i++) {
prev[i] = a[i - 1] * prev[i - 1];
}
int[] next = new int[a.length + 1];
next[a.length] = 1;
for (int i = a.length - 1; i >= 0; i--) {
next[i] = a[i + 1] * next[i + 1];
}
int[] res = new int[a.length];
for (int i = 0; i < prev.length; i++) {
res[i] = prev[i] * next[i];
}
return res;
}
|
复杂度分析 :
时间复杂度 : O(N) 线性遍历数组
空间复杂度 : O(N) 使用了额外的 prev 和 next数组存储空间
相比较第一种暴力法来说，这种解法在执行效率上就很优秀了。
思路三: 空间复杂度的优化
- 思路二，已经很好的解决了问题。 但是仍然有优化的空间
- 1，空间复杂度
- 题目进阶中有要求，是否可以使用 O(1) 空间复杂度解决问题？
- 2，循环次数
- 思路二，虽然是O(N)的时间复杂度，但是我们将数组遍历了 3 遍
- 是否可以减少遍历数组的次数？
- 下边这种解法，我们尝试进行上述两点的优化
- 初始化一个 res 数组，用于存储最终答案
- 在计算元素前边元素乘积时，将结果存入 res 数组
- 在计算元素后边元素乘积时，同步将结果存入 res 数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
/**
*
* 优化
* 1，空间复杂度
* 题目中进阶有要求
* 是否可以 O(1) 空间复杂度解决问题？
*
* 2, 循环次数
* 上述解法，我们遍历了3遍数组
* 是否可以少遍历一遍数组？
*
* 下边这种解法，我们尝试进行上述两点的优化
*
* [1,2,3,4,5]
* [120,60,40,30,24]
*
* [1,1,2,6,24]
* [,30,24]
* */
public int[] constructArr12int2(int[] a) {
if (a == null || a.length == 0) return a;
int[] res = new int[a.length];
res[0] = 1;
for (int i = 1; i < a.length; i++) {
res[i] = a[i - 1] * res[i - 1];
}
int R = 1;
for (int i = a.length - 1; i >= 0; i--) {
res[i] = res[i - 1] * R;
R *= res[i];
}
return res;
}
|
复杂度分析 :
时间复杂度 : O(N) 遍历了两遍数组, 时间复杂度 : O(N)
空间复杂度 : O(1) 题目中说，答案数组不被算作额外的存储空间，所以此解法，空间复杂度 O(1)
