线性时空实现数组各个元素除该位置外连乘

本文主要是介绍线性时空实现数组各个元素除该位置外连乘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素，即a[0]变为a[1]到a[n-1]的积，a[1]变为a[0]和a[2]到a[n-1]的积，...，a[n-1]为a[0]到a[n-2]的积（就是除掉当前元素，其他所有元素的积）。程序要求：具有线性复杂度，且不能使用除法运算符。

分析：

根据要求线性且不能用除法，那么就得需要分段线性策略，这道题如果能用除法的话就会非常简单，第一遍先对连乘数组所有元素，然后第二遍逐一除对应的数组元素！如果不能用除法，那么思想就得转换成将乘法分阶段，因而就产生了一种left和right算法，这也是题目本质解析，新的元素等于之前位置的左右元素连乘！第一遍我们只扫左边的连乘，第二遍扫右边的连乘，由于空间要求O(1)，因此我们可以使用第一个元素的特殊性做临时空间，因而无需再借助其他空间。

#include<iostream>
#include<stdio.h>
using namespace std;void multi_change(int a[],int b[],int n)
{b[0] = 1;for (int i = 1; i < n; i++)//begin index 1, left{b[0] *= a[i - 1];b[i] = b[0];}b[0] = 1;for (int i = n - 2; i>0; i--)//begin index n-2, right{b[0] *= a[i + 1];b[i] *= b[0];}b[0] *= a[1];
}int main()
{int a[5] = {1,2,3,4,5};int b[5];multi_change(a,b,5);for (int i = 0; i < 5;i++)printf("%d\t",b[i]);while (true){}return 0;
}

这篇关于线性时空实现数组各个元素除该位置外连乘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---