FF的泰普 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>bagua - 娱乐八卦

FF的泰普

FF的泰普# bagua - 娱乐八卦

a*l2013-04-23 07:04

1 楼

There is an array A[N] of N numbers. You have to compose an array Output[N]
such that Output[i] will be equal to multiplication of all the elements of A
[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N
-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n).
那位达人给说一个solution?

b*a2013-04-23 07:04

2 楼

http://www.jiaoyou8.com/friends_info?action=user_info&login_id=
小姨要努力转型了

s*x2013-04-23 07:04

3 楼

unit model? let x=10^k greater than the multiplication of all A[i], then
compute (x-A[1])(x^2-A[2])(x^4-A[3])....(x^(2^N/2)-A[N]) and some co-
efficient give the Output array.

]
A
[N

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

: There is an array A[N] of N numbers. You have to compose an array Output[N]
: such that Output[i] will be equal to multiplication of all the elements of A
: [N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N
: -1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
: Solve it without division operator and in O(n).
: 那位达人给说一个solution?

J*i2013-04-23 07:04

4 楼

吨位不及我

【在 b*a 的大作中提到】

: http://www.jiaoyou8.com/friends_info?action=user_info&login_id=
: 小姨要努力转型了

a*l2013-04-23 07:04

5 楼

怎么觉得不对呢

【在 s*x 的大作中提到】

: unit model? let x=10^k greater than the multiplication of all A[i], then
: compute (x-A[1])(x^2-A[2])(x^4-A[3])....(x^(2^N/2)-A[N]) and some co-
: efficient give the Output array.
:
: ]
: A
: [N

w*i2013-04-23 07:04

6 楼

那就努力减肥

【在 J********i 的大作中提到】

: 吨位不及我

c*g2013-04-23 07:04

7 楼

make two arrays L[i] and R[i]
where L[i] = Product of all elements left to i in A
So, A = [4,3,2,1,2]
Then, L = [1,4,12,24,24]
Similarly, R[i] is product of all elements to the right of i in A
R = [12,4,2,2,1]
Note that L and R can be calculated in O(n)
So, B[i] = L[i]*R[i] can be calculated in O(n)
B = [12, 16, 24, 48, 24]

J*i2013-04-23 07:04

8 楼

ff说我这样手感刚好

【在 w***i 的大作中提到】

: 那就努力减肥

c*g2013-04-23 07:04

9 楼

Note that L and R can be calculated in O(n)
So, B[i] = L[i]*R[i] can be calculated in O(n)

w*i2013-04-23 07:04

10 楼

恭
贺
排

【在 J********i 的大作中提到】

: ff说我这样手感刚好

m*f2013-04-23 07:04

11 楼

这是DP的思想阿，需要O(n) space. 原题有说space要求吗？ lz你的O(n)是指space还是time还是both...
可以有很多方法模拟division operator得，比如用左移法
1. 算出 N = A[0]*A[1]...A[n]
2. 要算output[i]
3. 循环把A[i] << 1直到大于N, 然后相减，然后重复, 最后得出结果
这里的复杂度是一个常数 log(N)

【在 c********g 的大作中提到】

: make two arrays L[i] and R[i]
: where L[i] = Product of all elements left to i in A
: So, A = [4,3,2,1,2]
: Then, L = [1,4,12,24,24]
: Similarly, R[i] is product of all elements to the right of i in A
: R = [12,4,2,2,1]
: Note that L and R can be calculated in O(n)
: So, B[i] = L[i]*R[i] can be calculated in O(n)
: B = [12, 16, 24, 48, 24]

d*e2013-04-23 07:04

12 楼

在啃嫩草?

【在 b*a 的大作中提到】

: http://www.jiaoyou8.com/friends_info?action=user_info&login_id=
: 小姨要努力转型了

g*y2013-04-23 07:04

13 楼

空间不是问题，因为既然要生成新的Output数组，就利用这个空间就够了。

space还是time还是both...

【在 m*****f 的大作中提到】

: 这是DP的思想阿，需要O(n) space. 原题有说space要求吗？ lz你的O(n)是指space还是time还是both...
: 可以有很多方法模拟division operator得，比如用左移法
: 1. 算出 N = A[0]*A[1]...A[n]
: 2. 要算output[i]
: 3. 循环把A[i] << 1直到大于N, 然后相减，然后重复, 最后得出结果
: 这里的复杂度是一个常数 log(N)

J*i2013-04-23 07:04

14 楼

哪里有嫩草

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

: 在啃嫩草?

m*f2013-04-23 07:04

15 楼

上述算法需要2O(n)空间, 所以严格来说还是不够啊

【在 g*******y 的大作中提到】

: 空间不是问题，因为既然要生成新的Output数组，就利用这个空间就够了。
:
: space还是time还是both...

d*e2013-04-23 07:04

16 楼

他叼着的

【在 J********i 的大作中提到】

: 哪里有嫩草