w*****k
发帖数: 20 | 1 Given an array A, output another array B such that B[k]=product of all
elements in A but A[k]. You are not allowed to use division。
显然interviewer是想考察一点什么技巧，一个直接的二重循环当然不是google想要的
答案。但是苦苦思索，没有头绪。请大侠赐教！
谢谢！ | t****a
发帖数: 1212 | 2 this is a problem listed in careercup 150. it need some trick and could be
done in O(n).
here is a python solution:
def convert(A):
left = [1]
for i in range(0, len(A)-1): left.append(left[-1]*A[i])
right = [1]
for i in range(1, len(A)): right.insert(0,right[0]*A[-i])
B = []
for i in range(0, len(A)): B.append(left[i]*right[i])
return B | h**k
发帖数: 3368 | 3 用这个公式
B[k]=Product(1,k-1) * Product(k+1, n)
Product(i,j) = A[i]*A[i+1]*...*A[j]
So Product(1,j)=Product(1,j-1)*A[j];
Prodcut(j,n)=Product(j+1,n)*A[j]
O(n)的时间和空间复杂度。
【在 w*****k 的大作中提到】
: Given an array A, output another array B such that B[k]=product of all
: elements in A but A[k]. You are not allowed to use division。
: 显然interviewer是想考察一点什么技巧，一个直接的二重循环当然不是google想要的
: 答案。但是苦苦思索，没有头绪。请大侠赐教！
: 谢谢！
| w*****k
发帖数: 20 | 4 谢谢！
【在 h**k 的大作中提到】
: 用这个公式
: B[k]=Product(1,k-1) * Product(k+1, n)
: Product(i,j) = A[i]*A[i+1]*...*A[j]
: So Product(1,j)=Product(1,j-1)*A[j];
: Prodcut(j,n)=Product(j+1,n)*A[j]
: O(n)的时间和空间复杂度。
| f****g
发帖数: 313 | 5 another very good and simple DP problem :S | A*********r
发帖数: 564 | 6 厉害。
【在 h**k 的大作中提到】
: 用这个公式
: B[k]=Product(1,k-1) * Product(k+1, n)
: Product(i,j) = A[i]*A[i+1]*...*A[j]
: So Product(1,j)=Product(1,j-1)*A[j];
: Prodcut(j,n)=Product(j+1,n)*A[j]
: O(n)的时间和空间复杂度。
|
|
