C ++中的产品数组难题？
在这里，我们将看到一个与数组有关的有趣问题。有一个包含n个元素的数组。我们必须创建另一个包含n个元素的数组。但是第二个数组的第i个位置将保存第一个数组除第i个元素以外的所有元素的乘积。一个约束是我们不能在该问题中使用除法运算符。
如果我们可以使用除法，运算，则可以通过获取所有元素的乘积轻松地解决此问题，然后将第一个数组的第i个元素除以并将其存储在第二个数组的第i个位置。
在这里，我们通过创建两个单独的数组来解决此问题。左右。left[i]将保存array[i]左边除array[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) {
//创建左右数组
int *left = new int[sizeof(int)*n];
int *right = new int[sizeof(int)*n];
//将left[]的第一个元素和right[]的最后一个元素设置为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];
}
//使用左右数组获取产品数组
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