a****l
发帖数: 245 | 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? | s*x
发帖数: 3328 | 2 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?
| a****l
发帖数: 245 | 3 怎么觉得不对呢
【在 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
| c********g
发帖数: 449 | 4 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] | c********g
发帖数: 449 | 5 Note that L and R can be calculated in O(n)
So, B[i] = L[i]*R[i] can be calculated in O(n) | m*****f
发帖数: 1243 | 6 这是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]
| g*******y
发帖数: 1930 | 7 空间不是问题，因为既然要生成新的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)
| m*****f
发帖数: 1243 | 8 上述算法需要2O(n)空间, 所以严格来说还是不够啊
【在 g*******y 的大作中提到】
: 空间不是问题，因为既然要生成新的Output数组，就利用这个空间就够了。
:
: space还是time还是both...
| g*******y
发帖数: 1930 | 9 不用。
第一遍，在output里算left数组
第二遍，用一个temp变量来算那个right数组，再乘到output数组上。
【在 m*****f 的大作中提到】
: 上述算法需要2O(n)空间, 所以严格来说还是不够啊
| c********g
发帖数: 449 | 10 2*O(N) =??
you might need to read "algothm analysis" textbook again.^_^ | | | c********g
发帖数: 449 | 11 >这里的复杂度是一个常数 log(N)
you might need to read "algothm analysis" textbook again also.^_^ | R***r
发帖数: 120 | 12 why not calculate the product of all elements in A, then output[i] = product
/ A[i], this seems much straight forward. | R***r
发帖数: 120 | 13 sorry, my bad, did not see no division allow. | m*****f
发帖数: 1243 | 14 N是乘积不是n,
看清楚点再说好么, 别动不动教训人, 最烦这样的
【在 c********g 的大作中提到】
: >这里的复杂度是一个常数 log(N)
: you might need to read "algothm analysis" textbook again also.^_^
| m*****f
发帖数: 1243 | 15 题目就提供一个数组空间的话, 你生成两组数不就是不够了
你根本不明白我的意思. 前面已经说了, 要用一个数组和一个变量, 所以你的
算法不完全对, 讨论的很清楚了
最烦你这样自以为是, 动不动居高临下教训人的, 自己再去学学礼貌这本书吧
【在 c********g 的大作中提到】
: 2*O(N) =??
: you might need to read "algothm analysis" textbook again.^_^
|
|
