j**l 发帖数: 2911 | 1 You are given an array [a1 ... an] and we have to construct another array [
b1 To bn] where bi = a1 * a2 * ... * an / ai. You are allowed to use only
constant
space and the time complexity is O(n). No divisions are allowed.
解法是引入两个辅助数组
Si = a1 * a2 * ... * ai
Ti = ai * a(i+1) * ... * an
则bi = S[i-1] * T[i+1]
但是有题目要求的O(1)空间和O(n)时间的解法么? |
l******e 发帖数: 6 | 2 1. for (i = 1:n-1)
b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
2. b[0] = b[1];
3. temp = a[0];
4. for (i = 1; i < n; i++)
{
b[i] = temp*b[i+1];
temp *= a[i];
}
Space: temp O(1);
Time: O(n)
【在 j**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You are given an array [a1 ... an] and we have to construct another array [ : b1 To bn] where bi = a1 * a2 * ... * an / ai. You are allowed to use only : constant : space and the time complexity is O(n). No divisions are allowed. : 解法是引入两个辅助数组 : Si = a1 * a2 * ... * ai : Ti = ai * a(i+1) * ... * an : 则bi = S[i-1] * T[i+1] : 但是有题目要求的O(1)空间和O(n)时间的解法么?
|
f*******e 发帖数: 1161 | 3 牛B!
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. for (i = 1:n-1) : b[i] = a[i]*a[i+1]*a[i+2]*...*a[n]; : 2. b[0] = b[1]; : 3. temp = a[0]; : 4. for (i = 1; i < n; i++) : { : b[i] = temp*b[i+1]; : temp *= a[i]; : } : Space: temp O(1);
|
j**l 发帖数: 2911 | 4 原来是要利用输出的数组b缓存辅助数组S和T的结果 |
f*******e 发帖数: 1161 | 5 好像不止这么简单
【在 j**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 原来是要利用输出的数组b缓存辅助数组S和T的结果
|
r****o 发帖数: 1950 | 6 问问,第1步求b[i]的过程实际上相当于O(n^2)吧。
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. for (i = 1:n-1) : b[i] = a[i]*a[i+1]*a[i+2]*...*a[n]; : 2. b[0] = b[1]; : 3. temp = a[0]; : 4. for (i = 1; i < n; i++) : { : b[i] = temp*b[i+1]; : temp *= a[i]; : } : Space: temp O(1);
|
j**l 发帖数: 2911 | 7 可以用例子说明,假如n = 5
首先让b从前向后一重循环累乘并赋值得到b的五个元素如下:
1, a1, a1*a2, a1*a2*a3, a1*a2*a3*a4
然后从后向前一重循环累乘
第五个元素乘1,
第四个元素乘a5
第三个元素乘a5*a4
第二个元素乘a5*a4*a3
第一个元素乘a5*a4*a3*a2 |
j**l 发帖数: 2911 | 8 假定n = 5,数组下标从1开始。
int iter = 1;
int i;
for (i = 1; i <= 5; i++)
{
b[i] = iter;
iter *= a[i];
}
iter = 1;
for (i = 5; i >= 1; i--)
{
b[i] *= iter;
iter *= a[i];
} |
m*****g 发帖数: 226 | 9 niu
【在 l******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. for (i = 1:n-1) : b[i] = a[i]*a[i+1]*a[i+2]*...*a[n]; : 2. b[0] = b[1]; : 3. temp = a[0]; : 4. for (i = 1; i < n; i++) : { : b[i] = temp*b[i+1]; : temp *= a[i]; : } : Space: temp O(1);
|
l******e 发帖数: 6 | 10 不好意思:第一步写错了。应该是:
1. for (i = n - 1; n > 0; i--)
b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
Sorry for the misleading.
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问问,第1步求b[i]的过程实际上相当于O(n^2)吧。
|
f****4 发帖数: 1359 | 11 这道题目是求 N个元素数组中 N-1个元素最大积吧?
求连续元素最大乘积的,能用辅助数组解决么?
O(n)的是记录最大,最小乘积 |
l*****a 发帖数: 14598 | 12 you r right.
【在 r****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问问,第1步求b[i]的过程实际上相当于O(n^2)吧。
|
d****n 发帖数: 233 | 13 it's O(n) if you do like this:
b[n-1] = a[n-1];
1. for (i = n-2:1)
b[i] = a[i]*b[i+1];
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you r right.
|
l*****a 发帖数: 14598 | 14 thanks
【在 d****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : it's O(n) if you do like this: : b[n-1] = a[n-1]; : 1. for (i = n-2:1) : b[i] = a[i]*b[i+1];
|