明天反恐24前总统Logan要出来 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

明天反恐24前总统Logan要出来 (转载)

明天反恐24前总统Logan要出来 (转载)# Joke - 肚皮舞运动

j*l2010-04-05 07:04

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)时间的解法么？

g*62010-04-05 07:04

2 楼

【以下文字转载自 CouchPotato 讨论区】
发信人: greatwar666 (KILL KILL KILL), 信区: CouchPotato
标题: 明天反恐24前总统Logan要出来
发信站: BBS 未名空间站 (Sun Apr 4 22:58:34 2010, 美东)
出来干什么？

l*e2010-04-05 07:04

3 楼

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 的大作中提到】

: 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*e2010-04-05 07:04

4 楼

牛B！

【在 l******e 的大作中提到】

: 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*l2010-04-05 07:04

5 楼

原来是要利用输出的数组b缓存辅助数组S和T的结果

f*e2010-04-05 07:04

6 楼

好像不止这么简单

【在 j**l 的大作中提到】

: 原来是要利用输出的数组b缓存辅助数组S和T的结果

r*o2010-04-05 07:04

7 楼

问问，第1步求b[i]的过程实际上相当于O(n^2)吧。

【在 l******e 的大作中提到】

: 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*l2010-04-05 07:04

8 楼

可以用例子说明，假如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*l2010-04-05 07:04

9 楼

假定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*g2010-04-05 07:04

10 楼

niu

【在 l******e 的大作中提到】

: 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*e2010-04-05 07:04

11 楼

不好意思：第一步写错了。应该是：
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 的大作中提到】

: 问问，第1步求b[i]的过程实际上相当于O(n^2)吧。