机器学习和生物信息学实验室联盟

标题: 做题：数组运算 [打印本页]
作者: tangzk    时间: 2012-4-20 13:27
标题: 做题：数组运算
本帖最后由 tangzk 于 2012-4-20 20:41 编辑

给定长度为N的两个数组a[]，b[]，要求不使用额外空间和除法运算，得出时间为O(n)的算法完成：
[attach]642[/attach]
作者: zouquan    时间: 2012-4-20 18:41
不使用额外空间还好办，不使用除法怎么算啊
作者: fiona    时间: 2012-4-20 19:49
那个公式是不是有问题呀？为什么数组a有N+1个元素，还有b[i]不就是除了第i个a元素的所有元素的乘积吗？
作者: chenwq    时间: 2012-4-20 19:50
本帖最后由 chenwq 于 2012-4-20 19:50 编辑

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;

  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.         }

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

是的，手一抽，公式写多了个等于了。呵呵，已经修正，谢谢师姐！
作者: tangzk    时间: 2012-4-20 21:24
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    时间: 2012-4-21 10:08
看走眼了。。。

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

厉害！
作者: chenwq    时间: 2012-4-22 14:52
fiona 发表于 2012-4-21 10:54
厉害！

您抬举了
作者: tangzk    时间: 2012-4-25 08:03
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这个空间也省掉呢？
作者: tangzk    时间: 2012-4-25 08:04
zouquan 发表于 2012-4-20 18:41
不使用额外空间还好办，不使用除法怎么算啊

呵呵，Tencent就出了这么一道伤脑细胞的题。



欢迎光临 机器学习和生物信息学实验室联盟 (http://123.57.240.48/) Powered by Discuz! X3.2