資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理
社會科學
時尚研究
法律研究C++ 中的產品陣列難題？
在此，我們將看到一個與陣列相關的有趣問題。有一個包含 n 個元素的陣列。我們必須建立另一個包含 n 個元素的陣列。但第二個陣列的第 i 個位置將儲存第一個陣列所有元素的乘積，不包括第 i 個元素。並且有一個限制，即我們不能在此問題中使用除法運算子。
如果我們可以使用除法運算，則我們可以輕鬆解決這個問題，方法是獲取所有元素的乘積，然後除以第一個陣列的第 i 個元素，並將其儲存在第二個陣列的第 i 個位置。
我們透過建立兩個單獨的陣列 left 和 right 來解決這個問題。left[i] 將儲存陣列[i] 左側所有元素（不包括陣列[i]）的乘積，right[i] 將儲存 arr[i] 右側所有元素（不包括 arr[i]）的乘積。此解決方案將花費 O(n) 時間。但它將佔用額外的空間。
演算法
productArray(arr, n)
begin define two arrays left and right of size n define an array called res of size n the first element of left and last element of right is set as 1 for i in range 1 to n, do left[i] = left[i-1] * arr[i-1] done for i in range n-1 down to 1, do right[i] = right[i+1] * arr[i+1] done for i in range 1 to n, do res[i] = left[i] * right[i]; done return res end
示例
#include<iostream>
using namespace std;
void printArray(int arr[], int n) {
for(int i = 0; i<n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void productArray(int arr[], int product[], int n) {
//create left right array
int *left = new int[sizeof(int)*n];
int *right = new int[sizeof(int)*n];
//set the first element of left[] and last element of right[] as 1
left[0] = right[n-1] = 1;
for(int i = 1; i<n; i++) {
left[i] = left[i-1] * arr[i-1];
}
for(int i = n-2; i>=0; i--) {
right[i] = right[i+1] * arr[i+1];
}
//get product array using left and right array
for(int i = 0; i<n; i++) {
product[i] = left[i] * right[i];
}
}
main() {
int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
int resArr[7];
cout << "Initial Array: ";
printArray(myArr, 7);
productArray(myArr, resArr, 7);
cout << "Final Array: ";
printArray(resArr, 7);
}輸出
Initial Array: 5 4 7 6 9 2 3 Final Array: 9072 11340 6480 7560 5040 22680 15120
更新於: 30-7-2019
191 次瀏覽
廣告