做题：数组运算

tangzk

给定长度为N的两个数组a[]，b[]，要求不使用额外空间和除法运算，得出时间为O(n)的算法完成：

zouquan

不使用额外空间还好办，不使用除法怎么算啊

fiona

那个公式是不是有问题呀？为什么数组a有N+1个元素，还有b[i]不就是除了第i个a元素的所有元素的乘积吗？

chenwq

b可以写成b1 * b2,其中b1=a[0]*a[1]...*a[i-1],b2=a[i+1]*a[i+2]...*a[N-1]，不计算其中的a，就相当于原式子除以a
然后，用两个循环，一个遍历b1，一个遍历b2

1. package cn.edu.xmu.acm.dp;
   
2. 
   
3. public class LP {
   
4.         void test(int a[], int b[], int n) {
   
5.                 int i;
   
6.                 int temp = 1;
   
7.                 temp = 1;                               
   
8.                 for (i = 1; i < n; i++) {
   
9.                         temp *= a[i - 1];               
   
10.                         b[i] = temp;
    
11.                 }
    
12.                 temp = 1;
    
13.                 for (i = n - 2; i > 0; i--) {
    
14.                         temp *= a[i + 1];       
    
15.                         b[i] *= temp;
    
16.                 }
    
17.                 b[0] = temp * a[1];
    
18.                 for (i = 0; i < n; i++) {
    
19.                         System.out.println(b[i]);
    
20.                 }
    
21.         }
    
22. 
    
23.         /**
    
24.          * @param args
    
25.          */
    
26.         public static void main(String[] args) {
    
27.                 LP lp = new LP();
    
28.                 int[] a = new int[10];
    
29.                 int[] b = new int[10];
    
30.                 for (int i = 0; i < 10; i++) {
    
31.                         a[i] = i+1;
    
32.                 }
    
33.                 lp.test(a, b, 10);
    
34.         }
    
35. }

复制代码

tangzk

fiona 发表于 2012-4-20 19:49
那个公式是不是有问题呀？为什么数组a有N+1个元素，还有b不就是除了第i个a元素的所有元素的乘积吗？

是的，手一抽，公式写多了个等于了。呵呵，已经修正，谢谢师姐！

tangzk

chenwq 发表于 2012-4-20 19:50
b可以写成b1 * b2,其中b1=a[0]*a[1]...*a,b2=a*a...*a[N-1]，不计算其中的a，就相当于原式子除以a
然后，用 ...

Good....  

xmubingo

看走眼了。。。

fiona

chenwq 发表于 2012-4-20 19:50
b可以写成b1 * b2,其中b1=a[0]*a[1]...*a,b2=a*a...*a[N-1]，不计算其中的a，就相当于原式子除以a
然后，用 ...

厉害！

chenwq

fiona 发表于 2012-4-21 10:54
厉害！

您抬举了

tangzk

chenwq 发表于 2012-4-20 19:50
b可以写成b1 * b2,其中b1=a[0]*a[1]...*a,b2=a*a...*a[N-1]，不计算其中的a，就相当于原式子除以a
然后，用 ...

可以在Line07设b[0]=1，后面Line17语句放入Line13-16循环内部，如下：

1. b[0] = 1;
   
2. for (int i = 1; i < N; i++) {
   
3.         b[i] = b[i - 1] * a[i - 1];
   
4. }
   
5. int temp = 1;
   
6. for (int i = N - 2; i >= 0; i--) {
   
7.         temp *= a[i + 1];
   
8.         b[i] *= temp;
   
9. }

复制代码

不过我也想，有没有可能把temp这个空间也省掉呢？