《剑指offer》:[52]构建乘积数组
发布时间：2020-12-13 21:10:52 所属栏目：PHP教程 来源：网络整理
导读：题目：给定1个数组A[0,1,2...N⑴],请构建1个数组B[0,2,...N⑴]，使B中的元素B[i]=A[0]*A[1]*...*A[i⑴]*a[i1]*...*a[n⑴]，不能使用除法。 解决思路： 通过正反两次来求B[i]; 正着：B[i]=A[0]*...A[i⑴]; 反着：temp = B[N]*...B[i1]; 最后通过B[i]*temp就能
|
题目：给定1个数组A[0,1,2...N⑴],请构建1个数组B[0,2,...N⑴]，使B中的元素B[i]=A[0]*A[1]*...*A[i⑴]*a[i+1]*...*a[n⑴]，不能使用除法。 解决思路：通过正反两次来求B[i]; 正着：B[i]=A[0]*...A[i⑴]; 反着：temp = B[N]*...B[i+1]; 最后通过B[i]*temp就能够求出结果了。 以A[0,3,4]，求B[0,4]为例： 步骤分析： 第1步：b[0] = 1; 第2步：b[1] = b[0] * a[0] = a[0] 第3步：b[2] = b[1] * a[1] = a[0] * a[1]; 第4步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2]; 第5步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3]; 然后对第2个for循环 第1步: temp *= a[4] = 1*a[4]; b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4]; 第2步: temp *= a[3] = a[4] * a[3]; b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3]; 第3步: temp *= a[2] = a[4] * a[3] * a[2]; b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2]; 第4步: temp *= a[1] = a[4] * a[3] * a[2] * a[1]; b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1]; 具体实现代码以下： #include <iostream>
using namespace std;
#include <vector>
vector<int> array1;
vector<int> array2(5);
void multiply(const vector<int> &array1,vector<int> &array2)
{
int length1=array1.size();
int length2=array2.size();
if(length1==length2 && length2>1)
{
array2[0]=1;
for(int i=1;i<length1;i++)
{
array2[i]=array2[i⑴]*array1[i⑴];
}
double temp=1;
for(int i=length1⑵;i>=0;i--)
{
temp*=array1[i+1];
array2[i]*=temp;
}
}
}
int main()
{
for(int i=0;i<5;i++)
array1.push_back(i+1);
multiply(array1,array2);
vector<int>::iterator it1;
vector<int>::iterator it2;
cout<<"A数组为：";
for(it1=array1.begin();it1!=array1.end();it1++)
cout<<*it1<<" ";
cout<<endl;
cout<<"B数组为：";
for(it2=array2.begin();it2!=array2.end();it2++)
cout<<*it2<<" ";
cout<<endl;
system("pause");
return 0;
}
主要是利用中间结果变量。运行结果：
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
