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

: 哪里有嫩草

g*y2013-04-23 07:04

17 楼

不用。
第一遍，在output里算left数组
第二遍，用一个temp变量来算那个right数组，再乘到output数组上。

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

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

J*i2013-04-23 07:04

18 楼

玫瑰啊，大妹子

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

: 他叼着的

c*g2013-04-23 07:04

19 楼

2*O(N) =??
you might need to read "algothm analysis" textbook again.^_^

d*e2013-04-23 07:04

20 楼

就看见几片叶子

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

: 玫瑰啊，大妹子

c*g2013-04-23 07:04

21 楼

>这里的复杂度是一个常数 log(N)
you might need to read "algothm analysis" textbook again also.^_^

J*i2013-04-23 07:04

22 楼

可能是边上有个女人，就剪掉了

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

: 就看见几片叶子

R*r2013-04-23 07:04

23 楼

why not calculate the product of all elements in A, then output[i] = product
/ A[i], this seems much straight forward.

R*r2013-04-23 07:04

24 楼

sorry, my bad, did not see no division allow.

m*f2013-04-23 07:04

25 楼

N是乘积不是n,
看清楚点再说好么, 别动不动教训人, 最烦这样的

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

: >这里的复杂度是一个常数 log(N)
: you might need to read "algothm analysis" textbook again also.^_^

m*f2013-04-23 07:04

26 楼

题目就提供一个数组空间的话, 你生成两组数不就是不够了
你根本不明白我的意思. 前面已经说了, 要用一个数组和一个变量, 所以你的
算法不完全对, 讨论的很清楚了
最烦你这样自以为是, 动不动居高临下教训人的, 自己再去学学礼貌这本书吧

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

: 2*O(N) =??
: you might need to read "algothm analysis" textbook again.^_^