计算a[0]*a[1]*...*a[n-1]/a[i]

Given an array a[n], build another array b[n], b[i] = a[0]*a[1]*...*a[n-1]/a[i]

no division can be used, O(n) time complexity


用Log后,用加减代替乘法和除法


我想到的是,开两个数组,一个记录从左到右的累积,一个记录从右到左的累积


更为巧妙的算法是:

voidarray_multiplication(intA[], intOUTPUT[], intn) {
 intleft = 1;
  intright = 1;
  for(inti = 0; i < n; i++)
  OUTPUT[i] = 1;
  for(inti = 0; i < n; i++) {
    OUTPUT[i] *= left;
    OUTPUT[n - 1 - i] *= right;
    left *= A[i];
    right *= A[n - 1 - i];
  }
}


左右扫描,正好交叉


http://leetcode.com/2010/04/multiplication-of-numbers.html

相关文章
相关标签/搜索