首页 > 代码库 > 已知一个数组a[N]来构造数组b[N]的有趣算法题
已知一个数组a[N]来构造数组b[N]的有趣算法题
给定一个数组a[N]，我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。
在构造过程要求满足：
1、不使用除法；
2、O(1)空间复杂度和O(n)时间复杂度；
3、除遍历a[N] b[N]使用的计数器外，不使用任何新的变量(包括栈临时变量、对空间和全局静态变量等)；
/**********************************************//*给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。在构造过程：1不允许使用除法；2要求O(1)空间复杂度和O(n)时间复杂度；3除遍历计数器与a[N] b[N]外，不可使用新的变量(包括栈临时变量、对空间和全局静态变量等)；*//**********************************************/void makeArray(int a[],int b[],int len){ int i,j; b[0] = 1; for(i=1;i<len;i++) { b[i] = b[i-1]*a[i-1]; //累乘a[0]*a[1]...a[i-1] } b[0] = a[len-1]; for(j=len-2;j>0;j--) { b[j] *= b[0]; b[0] *= a[j]; }}这道题目很常见，我看完之后分析了一下，如果在b[N]中，要求b[i]=a[0]*a[1]*...*a[N-1]/a[i]，那么我们可以分开考虑，实现代码用了两个循环，前一个循环先来实现，
b1[i]=a[0]a[1]a[2]…a[i-1],后一个循环从后往前来实现b2[i]=a[len-1]a[len-2]…a[i+1]，在第二个循环中由于b[0]的不断变化，实现了b[i]=b1[i]*b2[i]，所以才实现了题目要求，由于题目中不允许再定义变量可以将b[0]多次使用。
已知一个数组a[N]来构造数组b[N]的有趣算法题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。