構建乘積數組

06-27

構建乘積數組

來自專欄基礎演算法筆記

構建乘積數組

給定一個數組A[0,1...n-1],請構建一個數組B[0,1...n-1]，其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

思路:

C[i]=A[0]×A[1]×...×A[i-1]=C[i-1]×A[i-1]

D[i]=A[i+1]×...×A[n-1]=D[i+1]×A[i+1]

B[i]=C[i]×D[i]

參考代碼:

root@gt:/home/git/Code# ./a.out 120 60 40 30 24 root@gt:/home/git/Code# cat arrB.cpp #include <iostream>#include <vector>using namespace std;void multiply(vector<int>& arrA,vector<int>& arrB){ int lenA = arrA.size(); int lenB = arrB.size(); if(lenA == lenB && lenB > 1) { arrB[0] = 1; for(int i = 1;i < lenB;++i) arrB[i] = arrB[i-1] * arrA[i-1]; int temp = 1; for(int i = lenB-2;i >= 0;--i) { temp *= arrA[i+1]; arrB[i] *= temp; } }}int main(){ int tempA[] = {1,2,3,4,5}; vector<int> arrA(tempA,tempA+sizeof(tempA)/sizeof(int)); vector<int> arrB(5,1); multiply(arrA,arrB); for(vector<int>::iterator it = arrB.begin();it != arrB.end();++it) cout << *it << " "; cout << endl; return 0;}