某公司的一道笔试题的附加题，大家一起动动脑筋来看看

Question

题目大概是这样的：有两个数组a[N],b[N],求构造b[i]=a[0]*a[1]*a[2]*...a[N-1]/a[i],
要求：
1、不能使用除法。
2、空间复杂度O(1),时间复杂度O(n)。
3、除循环计数器和a[N]、b[N],不能使用其他变量。
用主流语言实现，讲讲想法。
大家动动脑筋，求大神指教，最好有代码。编程语言算法JavaC/C++笔试

Answer 1

不能使用除法的还没想出来
b[N - 1] = 1;for (int i = 0; i < N; ++i) {
    b[N-1] *= a[i];
}for (int i = 0; i < N; ++i) {
    b[i] *= b[N-1]/a[i];
}

Answer 2

题写错了吧，，不然 不用除法无解的 因为  b[i]=a[0]*a[1]*a[2]*...a[N-1]/a[i]
所以  b[N]=a[0]*a[1]*a[2]*...a[N-1]/a[N]  这个式子不用除法高低求不出啊

Answer 3

搞不明白 这道题目想在做什么
计算：b[i]=a[0]*a[1]*a[2]*...a[N-1]/a[i] 
1、不能使用除法。
2、空间复杂度O(1),时间复杂度O(n)。
3、除循环计数器和a[N]、b[N],不能使用其他变量。莫非我审题错误了？ a[N],b[N],数据大小都是N，Java中索引范围是1到N-1，b[i]=a[0]*a[1]*a[2]*...a[N-1]/a[i] 
求这个有什么意义吗？ 根本不用除法啊，搞不明白，a[0]*a[1]*a[2]*...a[N-1]做除数里面一定含有a[i],
真心不懂，用什么除法，

Answer 4

不用除法就可以的!
将a[i]=1;
改变一下公式b[i]=a[0]*a[1]*a[2]*.*a[i]..a[N-1]楼主是签了保密协议的,这样没问题吗?

Answer 5

i为输入参数
int j=0;
 b[i]=1;
 for j=0 to i-1
{
   if(j==i)
      continue;
   else
      b[i]=b[i]*a[j] 
}

Answer 6

我的理解是：当公式b[i]=a[0]*a[1]*a[2]*...a[N-1]运行到a[i]时跳过，就不要除法了.
由于变量问题以下的代码，我以a[j]表示a[j]，代码有点乱，请见谅for(int i=0;i<a.length;i++){
b[i]=a[0];
if(i==0)b[i]=1;
for(int j=1;j<a.length;j++){
if(i==j) continue;
b[i]*=a[j];
}
System.out.print(b[i]+"、");
}

Answer 7

不用除法，化简一下表达式就是这个样子：
b[i]=a[0]*a[1]*......*a[i-1]*a[i+1]*......*a[N];

Answer 8

y=1/x;;y=(x)^(-1).......;;调用系统求指数的函数Math.pow(double a, double b) 返回第一个参数的第二个参数次幂的值

Answer 9

for()
这个空间复杂度不符合啊。。

Answer 10

两重for循环时间复杂度O（n^2）貌似也不符合题目要求额

Answer 11

我就想问一下
就这个式子b[N]=a[0]*a[1]*a[2]*...a[N-1]/a[N]不用出发怎么求？？？
最简单的例子 数组 a是  一个 1到100的数  N=99 即 a[0]=1,a[1]=2,......a[99] =100b[n]=1*2*3*4*5*……*99/100   我想知道这个式子 扩展后  a[n]是个不确定个数的时候 怎么得出b[n]来b[0]-----b[n-1] 不用除法都有办法，，就这个 b[n]怎么求

Answer 12

public static void main(String[] args) {
final int a[] = new int[]{2,3,4,5,6};
final int N = a.length;
int b[] = new int[N];
b[0] = 1;
for(int i=1;i<N;i++){
b[i] = a[i-1] * b[i-1];
}
b[0] = 1;
for(int i=N-2;i>0;i--){
b[0] *= a[i+1];
b[i] *= b[0];
}
}

Answer 13

加了点注释
public static void main(String[] args) {
//初始化条件参数
final int a[] = new int[]{2,3,4,5,6};
final int N = a.length;
int b[] = new int[N];
//设置b[0]的初始值为1，用于以后的累乘
//乘积被i拆成两部分，所以，可用两个循环完成。
b[0] = 1;
//计算前半部分
for(int i=1;i<N;i++){
b[i] = a[i-1] * b[i-1];
}
//计算后半部分，b[0]充当临时变量。b[0] = 1;
for(int i=N-2;i>0;i--){
b[0] *= a[i+1];
b[i] *= b[0];
}
}

Answer 14

  public static void main(final String[] args) {
    final int[] a = new int[]{34, 45, 3, 62, 2, 43, 6, 4, 1, 949};
    final int n = a.length;    int[] b = new int[n];    b[0] = a[n - 1];
    for (int i = 1; i < n; i++) {
      b[i] *= b[i - 1] * a[i - 1];
    }    b[n - 1] = 1;
    for (int i = 1; i < n; i++) {
      b[n - 1] *= a[n - 1 - i];
      b[n - 1 - i] *= b[n - 1];
    }
  }写出来才发现跟楼上的差不多，只是我把b[n -1]当做临时变量

Answer 15

有点低烧，起来晚了，昨天半夜看的题目，早上就想起这个解法了。不过这个做法b[0]是不对的，两种修补方案，
1，再算一次b[0]=a[1]....a[n]，建议这种。
2，变动a，让a承担计算后面乘积的功能。这个也是我一觉醒来，直接想到的方法：  public static void main(String[] args) {
    int[] a = new int[] {
        2, 3, 5, 7, 9, 11, 13, 17, 19
    };
    System.out.println(Arrays.toString(a));
    int[] b1 = foo(a);
    System.out.println(Arrays.toString(b1));
    int[] b2 = bar(a);
    System.out.println(Arrays.toString(b2));
  }  // O(N^2)
  public static int[] foo(int[] a) {
    int[] b = new int[a.length];
    Arrays.fill(b, 1);
    for (int i =0; i < a.length; i++) {
      for (int j = 0; j < a.length; j++) {
        b[i] *= (i==j) ? 1 : a[j];
      }
    }
    return b;
  }
  
  // O(N)
  public static int[] bar(int[] a) {
    int[] b = new int[a.length];
    b[0] = 1;
    for (int i = 1; i < a.length; i++) {
      b[i] = b[i - 1] * a[i - 1];
    }
    for (int i = a.length - 1; i-- > 0;) {
      a[i] *= a[i + 1];
    }
    for (int i = 0; i < a.length - 1; i++) {
      b[i] *= a[i + 1];
    }
    return b;
  }

Answer 16

int[] a = {1,1,2,3,1,1,1,1,1,1};
int[] b = new int[10];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length-1; j++) {
if(i!=j){
if(j==0){
b[i]=a[j];
}else{
b[i]*=a[j];
}
}
}
}
for (int i = 0; i < b.length; i++) {
System.out.println(b[i]);
}
简单的列子，是像这样的么？

Answer 17

http://bbs.csdn.net/topics/390433361?page=1#post-39426747712楼正解

Answer 18

LZ, 21F加上我24F的修正方案1或者我直接贴出的修正代码2，都是O(N)的一段代码，即便是x次O(N)的循环，只要x是常量，与N无关，整个代码都是O(N)的

Answer 19

这道题，是谷歌面试题，原题中没有要求空间复杂度。给你一个数组 A [ 1 .. n ] ，请你在 O ( n ) 的时间里构造一个新的数组 B [ 1 .. n ] ，使得 B [ i ] = A [ 1 ] * A [ 2 ] * ... * A [ n ]／A [ i ] 。你不能使用除法运算。
B [ i ] 不用除法来表示的话就是： B [ i ] = A [ 1 ] * ... * A [ i - 1 ] * A [ i + 1 ] * ... * A [ n ] 。若按照这个表达式进行计算，生成每个 B[ i ] 的时候要进行n - 1次乘法，这样一来完全生成 B [ 1 .. n ] 就需要 O ( n 2 ) 的时间了。我们需要通过减少重复的运算来提高效率。注意到 B [ i ] 可以看作是两个部分的乘积， A [ 1 ] * ... * A [ i - 1 ] 和 A [ i + 1 ] * ... * A [ n ] 。同理 B [ i + 1 ] 就由 A [ 1 ] * ... * A [ i - 1 ] * A [ i ] 和 A [ i + 2 ] * ... * A [ n ] 组成。计算 B [ i ] 时的许多乘法在计算 B [ i + 1 ] 的时候又进行了一遍，因此可以重复利用上一次运算的结果，以避免无谓的运算。从这点出发，我们构造两个新的数列：S [ i ] = A [ 1 ] * ... * A [ i – 1 ]T [ i ] = A [ i + 1 ] * ... * A [ n ]因为生成完整的 S [ 1 .. n ] 和 T [ 1 .. n ] 都能在 O ( n ) 的时间内完成，那么根据 B [ i ] = S [ i ] * T [ i ] 这条式子，生成整个 B [ 1 .. n ] 便也能够在 O ( n ) 的时间内完成了。
顺便坦克哥+1